Dijkstra's shortest path - Programmers Heaven

Howdy, Stranger!

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

Categories

Dijkstra's shortest path

pcs2112pcs2112 Posts: 5Member
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

  • IDKIDK Posts: 1,784Member
    Please formulate your problem.
  • pcs2112pcs2112 Posts: 5Member
    : 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]
  • IDKIDK Posts: 1,784Member
    : : Please formulate your problem.
    :
    : need help understanding how to code
    :

    Hmm..., haven't you done that already? (coded, that is)
  • pcs2112pcs2112 Posts: 5Member
    : : : 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
  • IDKIDK Posts: 1,784Member
    : : : : 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.