<分区>
我搜索了 Dijkstra 的全对最短路径的 Java 实现。 我找到了一个源最短路径的算法。我其实不懂Java，但我正在研究离散数学，所以也许有人可以帮助我。我必须改变什么才能使其成为全对最短路径？
------------编辑-------- 再次感谢 templatetypedef。我试试现在我认为代码中还有一个小错误。
输入文件(try.txt):
0 2 68
3 4 97
0 3 8
这是我得到的错误输出:
From 3:
Shortest Path Cost to 3 is: 0.0
Shortest Path Cost to 2 is: Infinity
Shortest Path Cost to 0 is: Infinity
Shortest Path Cost to 4 is: 97.0
From 2:
Shortest Path Cost to 3 is: Infinity
Shortest Path Cost to 2 is: 0.0
Shortest Path Cost to 0 is: Infinity
Shortest Path Cost to 4 is: 97.0
From 0:
Shortest Path Cost to 3 is: 8.0
Shortest Path Cost to 2 is: 68.0
Shortest Path Cost to 0 is: 0.0
Shortest Path Cost to 4 is: 97.0
From 4:
Shortest Path Cost to 3 is: 8.0
Shortest Path Cost to 2 is: 68.0
Shortest Path Cost to 0 is: Infinity
Shortest Path Cost to 4 is: 0.0
代码:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
class Vertex implements Comparable<Vertex> {
public final String name;
public List<Edge1> adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) {
name = argName;
adjacencies = new ArrayList<Edge1>();
}
public void addEdge(Edge1 e) {
adjacencies.add(e);
}
public String toString() {
return name;
}
public int compareTo(Vertex other) {
return Double.compare(minDistance, other.minDistance);
}
}
class Edge1{
public final Vertex target;
public final double weight;
public Edge1(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 (Edge1 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[]) {
Map<String, Vertex> vertexMap = new HashMap<String, Vertex>();
BufferedReader in = null;
try {
in = new BufferedReader(new FileReader("try.txt"));
String line;
boolean inVertex = true;
while ((line = in.readLine()) != null) {
//store the edges
String[] parts = line.split(" ");
String vFrom = parts[0];
String vTo = parts[1];
if(!vertexMap.containsKey(vFrom))
{
Vertex v= new Vertex(vFrom);
vertexMap.put(vFrom, v);
}
if(!vertexMap.containsKey(vTo))
{
Vertex v1= new Vertex(vTo);
vertexMap.put(vTo, v1);
}
double weight = Double.parseDouble(parts[2]);
Vertex v = vertexMap.get(vFrom);
if (v != null) {
v.addEdge(new Edge1(vertexMap.get(vTo), weight));
}
}
} catch (IOException e) {
e.printStackTrace();
return;
}
finally{
if(in!= null)
try {
in.close();
} catch (IOException ignore) {
}
}
//get a list of all the vertices
Collection<Vertex> vertices = vertexMap.values();
//Vertex source = vertices.iterator().next();
for(Vertex source:vertices){
System.out.println("From " + source+":");
computePaths(source);
for (Vertex v : vertices) {
System.out.println("Shortest Path Cost to " + v + " is: " + v.minDistance);
// List<Vertex> path = getShortestPathTo(v);
// System.out.println("Path: " + path);
}System.out.println();
source.minDistance=Double.POSITIVE_INFINITY;
source.previous=null;}
}
}