Dijkstra's shortest path

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

[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[u] + length(u, v)
11 if alt < dist[v] // Relax (u,v)
12 dist[v] := alt
13 previous[v] := u
14 return previous[]
[/code]

[code]
public static void Dijkstra(airportGraph g, Vertex v){

ArrayList 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());
}

}
}
}
[/code]

my vertex class has these fields

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


Comments

  • Please formulate your problem.
  • : Please formulate your problem.

    need help understanding how to code

    [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[]
    [/code]
  • : : Please formulate your problem.
    :
    : need help understanding how to code
    :

    Hmm..., haven't you done that already? (coded, that is)
  • : : : 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
  • : : : : 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.
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories