A little help needed with Dijkstra's algorithim
Hi I'm trying to implement Dijkstra's algorithm. I have a class GraphMaker
which creates the graph, and is the main console. And then a second class for Dijkstra's algorithm. Overall it works alright but, I can't to figure out how to get it to find the shortest path for all the cities.
Here's a sample output:
BOSTON To NEW YORK: Cost of: 22 MIAMI: Cost of: 122
NEW YORK To MIAMI: Cost of: 50 HONOLULU : Cost of: 422
DETROIT To CHICAGO: Cost of: 22 PHOENIX: Cost of: 62
MIAMI To HONOLULU : Cost of: 402
CHICAGO To
PHOENIX To
HONOLULU To DETROIT: Cost of: 302 PHOENIX: Cost of: 102
[BOSTON -> ]
[BOSTON -> , NEW YORK>]
[BOSTON -> , NEW YORK>, HAWAII>, DETROIT>]
[BOSTON -> , NEW YORK>, MIAMI>]
[BOSTON -> , NEW YORK>, HAWAII>,CHICAGO>]
[BOSTON -> , NEW YORK>, HAWAII>, PHOENIX>]
[BOSTON -> , NEW YORK>, HAWAII>]
I know its not the most efficient looking output, I'm intermediate coder at best. But at the top you have 7 cities from BOSTON to HONOLULU, and the cities they connect to. Where I'm really having the problem is at the bottom part. It shows the shortest paths from Boston to other the cities. But I want it show not only the shortest paths from Boston but also the shortest paths from the other cities, to their destination.
Here's my code:
The GraphMaker Class:
publicclass GraphMaker{
privateint [][] edges;// The adjacency matrix
private Object [] Cities;// Cities
publicstaticint count;
public GraphMaker (int n){
edges =newint [n][n];
Cities =new Object[n];
}
publicint GetSize()
{
return Cities.length;
}
publicvoidSetCities (int vertex, Object label)
{
Cities[vertex]=label;
}
public Object GetCities (int vertex)
{
return Cities[vertex];
}
publicvoid AddEdge (int source,int target,int w)
{
edges[source][target] = w;
}
publicboolean IsEdge (int source,int target)
{
return edges[source][target]>0;
}
publicvoid RemoveEdge (int source,int target)
{
edges[source][target] = 0;
}
publicint GetWeight (int source,int target)
{
return edges[source][target];
}
publicint [] Neighbors (int vertex){
count = 0;
for (int i=0; i<edges[vertex].length; i++){
if (edges[vertex][i]>0) count++;
}
finalint[]answer=newint[count];
count = 0;
for (int i=0; i<edges[vertex].length; i++){
if (edges[vertex][i]>0) answer[count++]=i;
}
return answer;
}
publicvoid print (){
for (int j=0; j<edges.length; j++){
System.out.print (Cities[j]+"To");
for (int i=0; i><edges[j].length; i++){
if (edges[j][i]>0) System.out.print (Cities[i]+": Cost of: " +
"" + edges[j][i]+"");
}
System.out.println (" ");
}
}
publicstaticvoid main (String args[]){
GraphMaker t =new GraphMaker (7);
t.SetCities (0,"BOSTON");
t.SetCities(1,"NEW YORK");
t.SetCities (2,"DETROIT");
t.SetCities (3,"MIAMI");
t.SetCities (4,"CHICAGO");
t.SetCities (5,"PHOENIX");
t.SetCities (6,"HAWAII");
t.AddEdge (0,1,22);
t.AddEdge (1,6,422);
t.AddEdge (0,3,122);
t.AddEdge (2,4,22);
t.AddEdge (2,5,62);
t.AddEdge (6,5,102);
t.AddEdge (3,6,402);
t.AddEdge (6,2,302);
t.AddEdge (1,3,50);
t.print();
finalint [] pred = Dijkstra.dijkstra (t, 0);
for (int n=0; n<7; n++){
Dijkstra.PrintPath (t, pred, 0, n);
}
}
}
And my Dijkstra class
import java.util.LinkedList;
publicclass Dijkstra{
publicstaticint [] dijkstra (GraphMaker G,int s){
finalint [] dist =newint [G.GetSize()];// shortest known distance from "s"
finalint [] pred =newint [G.GetSize()];// the node that preceeds it in the path
finalboolean [] visited =newboolean [G.GetSize()];// all false initially
for (int i=0; i<dist.length; i++){
dist[i] = Integer.MAX_VALUE;
}
dist[s] = 0;
for (int i=0; i><dist.length; i++){
finalint next = SmallestVertex (dist, visited);
visited[next] =true;
finalint [] n = G.Neighbors (next);
for (int j=0; j><n.length; j++){
finalint v = n[j];
finalint d = dist[next] + G.GetWeight(next,v);
if (dist[v] > d){
dist[v] = d;
pred[v] = next;
}
}
}
return pred;
}
privatestaticint SmallestVertex (int [] dist,boolean [] v){
int x = Integer.MAX_VALUE;
int y = -1;
for (int i=0; i<dist.length; i++){
if (!v[i] && dist[i]><x){y=i; x=dist[i];}
}
return y;
}
publicstaticvoid PrintPath (GraphMaker G,int [] pred,int s,int e){
final LinkedList path =new LinkedList();
int x = e;
while (x!=s){
path.add (0, G.GetCities(x) +">");
x = pred[x];
}
path.add (0, G.GetCities(s) +" -> ");
System.out.println (path);
}
}
