'Dijkstra's shortest path' Thread RSS Feed

Dijkstra's shortest path

Wed, 19 Dec 2007 08:32:51 -0700

i'm stuck translating this pseudo code from wikipedia to java...can anybody help me......

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from s to v
 4          previous[v] := undefined
 5      dist[source] := 0                     // Distance from s to s
 6      Q := copy(Graph)                      // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := extract_min(Q)               // Remove best vertex from priority queue; returns source on first iteration
 9          for each neighbor v of u:         // where v has not yet been considered
10              alt = dist + length(u, v)
11              if alt < dist[v]              // Relax (u,v)
12                  dist[v] := alt
13                  previous[v] := u
14      return previous[]

public static void Dijkstra(airportGraph g, Vertex v){
		
		ArrayList<Vertex> vertices = g.vertexList;
		
		for (Vertex u : vertices){
			if (u.getName().equals(v.getName()))
				u.setDistance(0);
			else
				u.setDistance(Integer.MAX_VALUE);
		}
		
		PriorityQueue Q = new PriorityQueue(6);
		
		for (Vertex u : vertices)
			Q.enqueue(u);
		
		Vertex u;
		
		while(!Q.isEmpty()){
			u = Q.dequeue();
			for (Edge e: g.incidentEdges(u)) {
				Vertex z = g.opposite(u,e); /// chekc this

				  if ( u.getDistance() + e.getWeight() < z.getDistance() ){
					  z.setDistance(u.getDistance() + e.getWeight());
				  }
				  
			}
		}
	}

my vertex class has these fields

private String name;
private boolean visited;
private int location;
private Integer distance;

Re: Dijkstra's shortest path

Wed, 19 Dec 2007 09:32:41 -0700

Please formulate your problem.

Re: Dijkstra's shortest path

Wed, 19 Dec 2007 09:44:48 -0700

: Please formulate your problem.

need help understanding how to code

1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from s to v
 4          previous[v] := undefined
 5      dist[source] := 0                     // Distance from s to s
 6      Q := copy(Graph)                      // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := extract_min(Q)               // Remove best vertex from priority queue; returns source on first iteration
 9          for each neighbor v of u:         // where v has not yet been considered
10              alt = dist + length(u, v)
11              if alt < dist[v]              // Relax (u,v)
12                  dist[v] := alt
13                  previous[v] := u
14      return previous[]

Re: Dijkstra's shortest path

Wed, 19 Dec 2007 10:19:23 -0700

: : Please formulate your problem.
:
: need help understanding how to code
:

Hmm..., haven't you done that already? (coded, that is)

Re: Dijkstra's shortest path

Wed, 19 Dec 2007 10:22:26 -0700

: : : Please formulate your problem.
: :
: : need help understanding how to code
: :
:
: Hmm..., haven't you done that already? (coded, that is)
:

its not working becasue i think im mising something

Re: Dijkstra's shortest path

Wed, 19 Dec 2007 11:48:27 -0700

: : : : Please formulate your problem.
: : :
: : : need help understanding how to code
: : :
: :
: : Hmm..., haven't you done that already? (coded, that is)
: :
:
: its not working becasue i think im mising something
:

If I'm not missing something, you're missing the previous array.