Dijkstra算法寻找最短路径

Question

我需要帮助给写Dijkstra算法代码，通过使用Java寻找最短路径，并且只使用这个版本如下：

**程序的Dijkstra（G，W，R，父[0：N-1]，DIST）

当v←0到n-1做

DIST [v]←∞

InTheTree [v]←.FALSE。

ENDFOR

父[R]←-1

DIST [R]←0

在水位←1到n-1做

选择顶点u最小化DIST [你在所有你这样的InTheTree [U] = .false。

InTheTree [u] = .true。 //外接U到T

为每个顶点v，使得UV∈e执行//更新DIST [V]和

如果。不。 InTheTree [V]的情况then //父[V]数组

如果DIST [U]←W（UV）< DIST [V]然后

DIST [V] = DIST [U] + W（UV）

最近[v]←（）

父[R]←ü

ENDIF

ENDIF

ENDFOR

ENDFOR

末的Dijkstra **

..................... 感谢

Answer 1

ArgoList有一个实现我刚刚GOOGLE：

import java.util.PriorityQueue; 
import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 

class Vertex implements Comparable<Vertex> 
{ 
public final String name; 
public Edge[] adjacencies; 
public double minDistance = Double.POSITIVE_INFINITY; 
public Vertex previous; 
public Vertex(String argName) { name = argName; } 
public String toString() { return name; } 
public int compareTo(Vertex other) 
{ 
    return Double.compare(minDistance, other.minDistance); 
} 
} 

class Edge 
{ 
public final Vertex target; 
public final double weight; 
public Edge(Vertex argTarget, double argWeight) 
{ target = argTarget; weight = argWeight; } 
} 

public class Dijkstra 
{ 
public static void computePaths(Vertex source) 
{ 
    source.minDistance = 0.; 
    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); 
    vertexQueue.add(source); 

while (!vertexQueue.isEmpty()) { 
    Vertex u = vertexQueue.poll(); 

     // Visit each edge exiting u 
     for (Edge e : u.adjacencies) 
     { 
      Vertex v = e.target; 
      double weight = e.weight; 
      double distanceThroughU = u.minDistance + weight; 
    if (distanceThroughU < v.minDistance) { 
     vertexQueue.remove(v); 
     v.minDistance = distanceThroughU ; 
     v.previous = u; 
     vertexQueue.add(v); 
    } 
     } 
    } 
} 

public static List<Vertex> getShortestPathTo(Vertex target) 
{ 
    List<Vertex> path = new ArrayList<Vertex>(); 
    for (Vertex vertex = target; vertex != null; vertex = vertex.previous) 
     path.add(vertex); 
    Collections.reverse(path); 
    return path; 
} 

public static void main(String[] args) 
{ 
    Vertex v0 = new Vertex("Redvile"); 
Vertex v1 = new Vertex("Blueville"); 
Vertex v2 = new Vertex("Greenville"); 
Vertex v3 = new Vertex("Orangeville"); 
Vertex v4 = new Vertex("Purpleville"); 

v0.adjacencies = new Edge[]{ new Edge(v1, 5), 
          new Edge(v2, 10), 
          new Edge(v3, 8) }; 
v1.adjacencies = new Edge[]{ new Edge(v0, 5), 
          new Edge(v2, 3), 
          new Edge(v4, 7) }; 
v2.adjacencies = new Edge[]{ new Edge(v0, 10), 
          new Edge(v1, 3) }; 
v3.adjacencies = new Edge[]{ new Edge(v0, 8), 
          new Edge(v4, 2) }; 
v4.adjacencies = new Edge[]{ new Edge(v1, 7), 
          new Edge(v3, 2) }; 
Vertex[] vertices = { v0, v1, v2, v3, v4 }; 
    computePaths(v0); 
    for (Vertex v : vertices) 
{ 
    System.out.println("Distance to " + v + ": " + v.minDistance); 
    List<Vertex> path = getShortestPathTo(v); 
    System.out.println("Path: " + path); 
} 
} 
}