I've recently read the algorithm for Dijkstra's Shortest Path, but I'm not quite sure if I fully understand it at both a conceptual/programming level. This being said, I have made the program in java, but it's limited in terms of flexibility as well as efficiency. It would be highly appreciated if my code was read and perhaps commented on (in terms of what I can do better, or perhaps comment on my logic), and if anyone could just explain how the algorithm works/how to program it, that would be very much appreciated. Thanks ^^
Code:
import java.util.*;
public class ShortestPath {
public static void main(String[] args) {
new ShortestPath().run();
}
private void run() {
String graph [][]=
{
{"A","B","C","D","E","F"}, //1) Head Nodes
{"B","C","B","E","C","C"}, //2) Connection Nodes
{"" ,"A","E","C","D","" }, //3) Connection Nodes
{"" ,"" ,"F","" ,"" ,"" }, //4) Connection Nodes
{"" ,"" ,"D","" ,"" ,"" }, //5) Connection Nodes
};
int dist [] = {1,5,1,5,3,7,1,2,1,3,2,7};
String source = "A";
String goal = "F";
System.out.println(
Path(graph, dist, source, goal)
);
}
/*
Computer Graph ([j1][i1-->i6] = Head Nodes (Each section of the Paper/Pencil graph))
i1 i2 i3 i4 i5 i6
j1 {"A","B","C","D","E","F"}
j2 {"B","C","B","E","C","C"}
j3 {"" ,"A","E","" ,"D","" }
j4 {"" ,"" ,"F","" ,"" ,"" }
Pencil/Paper Graph
A--1-->B
B--5-->C
B--1-->A
C--5-->B
C--1-->D
C--3-->E
C--7-->F
D--1-->C
D--2-->E
E--3-->C
E--2-->D
F--7-->C
*/
public int Path (String graphx [][], int distx [], String source, String goal){
// *Variables*
int Shortest=0;
HashMap <String, Integer> path = new HashMap <String, Integer>();
int count = 0;
int cost;
String graph[][];
int dist [];
int start=0;
// *Variables*
for (int i = -1;++i < 6;)if (graphx[0][i].equals(source))start = i;
graph = copy2DArray(graphx,start,6);
dist = copy1DArray(distx,0);
path.put(source, 0);
for (int i = 0; ++i < 6
{
if (!graph[0][i].equals(source))
path.put(graph[0][i], Integer.MAX_VALUE); //Integer.MAX_VALUE = ∞
}
for (int i = -1; ++i < 6
{
cost = path.get(graph[0][i]);
for (int j = -1; ++j < graph.length;){
if (!graph[j][i].equals("") & j > 0){
if (dist[count] + cost < path.get(graph[j][i]))
path.put(graph[j][i], dist[count]+cost);
count++;
}
}
}
Shortest = path.get(goal);
return Shortest;
}
public String [][] copy2DArray (String[][] a, int start, int maxLength){
String [][] retArray = new String [a.length][maxLength];
int retCount = 0;
for (int i = start-1; ++i < maxLength;){
for (int j = -1; ++j < a.length;){
retArray[j][retCount] = a[j][i];
}
retCount++;
}
for (int i = -1; ++i < start;){
for (int j = -1; ++j < a.length;){
retArray[j][retCount] = a[j][i];
}
retCount++;
}
return retArray;
}
public int [] copy1DArray (int [] a, int start){
int [] retArray = new int [a.length];
int retCount = 0;
for (int i = start-1;++i < a.length;){
retArray[retCount] = a[i];
retCount++;
}
for (int i = -1; ++i < start;){
retArray[retCount] = a[i];
retCount++;
}
return retArray;
}
}