Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Dijkstra Shortest Path
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
fastftw




PostPosted: Sun Dec 02, 2012 4:23 pm   Post subject: Dijkstra Shortest Path

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 < 6Wink{
if (!graph[0][i].equals(source))
path.put(graph[0][i], Integer.MAX_VALUE); //Integer.MAX_VALUE = ∞
}

for (int i = -1; ++i < 6Wink{
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;
}

}
Sponsor
Sponsor
Sponsor
sponsor
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 1 Posts ]
Jump to:   


Style:  
Search: