我正在尝试为 Dijkstra 最短路径算法编写自己的代码，基于我在以下网站上找到的伪代码： https://www.freecodecamp.org/news/dijkstras-algorithm-explained-with-a-pseudocode-example/
但是，当将我的代码实现的结果与 JGraphT 库中的 DijksraShortestPath 实现进行比较时，结果是不同的。我希望我的代码与 JGraphT 实现的结果相匹配。
这是我的代码：
package pckg;
import java.util.ArrayList;
import java.util.Set;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm.SingleSourcePaths;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultUndirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
public class Dijkstra {
static DefaultUndirectedWeightedGraph<String, DefaultWeightedEdge> map = Map.createMap();
public static void main(String[] args) {
DijkstraShortestPath<String, DefaultWeightedEdge> test = new DijkstraShortestPath<String, DefaultWeightedEdge>(map);
SingleSourcePaths<String, DefaultWeightedEdge> paths = test.getPaths("0");
ArrayList<double[]> dijkstraData = dijkstra(map, 0);
double[] dist = dijkstraData.get(0);
double[] pred = dijkstraData.get(1);
for (int i = 0; i <= 35; i++) {
String s = Integer.toString(i);
System.out.println(
"JGraphT: " + paths.getWeight(s) +
" - My code: " + dist[i]);
}
}
public static ArrayList<double[]> dijkstra(DefaultUndirectedWeightedGraph<String, DefaultWeightedEdge> graph, int source) {
final double inf = 1.0/0.0; //dividing by zero gives infinity
double[] dist = new double[ graph.vertexSet().size() ];
double[] pred = new double[ graph.vertexSet().size() ];
ArrayList<Integer> Q = new ArrayList<Integer>(0);
Set<String> vertexSet = graph.vertexSet();
for (String vString : vertexSet) { //for each vertex v in Graph.Vertices:
int v = Integer.parseInt(vString);
dist[v] = inf; //dist[v] ← INFINITY
pred[v] = -1; //prev[v] ← UNDEFINED
Q.add(v); //add v to Q
}
dist[source] = 0; //dist[source] ← 0
while (!Q.isEmpty()) { //while Q is not empty:
// Find minimum element in Q based on dist values
int min = Q.get(0);
for (int i : Q) {
if (dist[i] < dist[min]) {
min = i;
}
}
int u = min; //u ← vertex in Q with min dist[u]
Q.remove(Integer.valueOf(u)); // Remove u from Q
ArrayList<Integer> neighbours = new ArrayList<Integer>(0);
for (int node : Q) { //for each neighbor v of u still in Q:
//get all neighbours of of u still in Q
Set<DefaultWeightedEdge> edges = graph.edgesOf(Integer.toString(node));
for (DefaultWeightedEdge edge : edges)
if (!neighbours.contains( Integer.parseInt( graph.getEdgeTarget(edge) ) ))
neighbours.add( Integer.parseInt( graph.getEdgeTarget(edge) ) );
}
for (int v : neighbours) { // for each neighbor v of u still in Q:
DefaultWeightedEdge edge = graph.getEdge(Integer.toString(u), Integer.toString(v));
if (edge == null) { continue; } //check if edge exists
//System.out.println(edge.toString());
double alt = dist[u] + graph.getEdgeWeight( edge ); //alt ← dist[u] + Graph.Edges(u, v)
if (alt < dist[v] ) { //if alt < dist[v]:
dist[v] = alt; //dist[v] ← alt
pred[v] = u; // prev[v] ← u
}
}
}
ArrayList<double[]> returnData = new ArrayList<double[]>(0);
returnData.add(dist);
returnData.add(pred);
return returnData;
}
}
结果如下：
JGraphT: 0.0 - My code: 0.0
JGraphT: 633.0 - My code: Infinity
JGraphT: 551.0 - My code: 551.0
JGraphT: 421.0 - My code: 421.0
JGraphT: 352.0 - My code: 352.0
JGraphT: 305.0 - My code: 305.0
JGraphT: 250.0 - My code: 250.0
JGraphT: 304.0 - My code: 304.0
JGraphT: 662.0 - My code: 662.0
JGraphT: 702.0 - My code: 773.0
JGraphT: 506.0 - My code: 506.0
JGraphT: 438.0 - My code: 438.0
JGraphT: 381.0 - My code: 381.0
JGraphT: 341.0 - My code: 341.0
JGraphT: 698.0 - My code: 698.0
JGraphT: 710.0 - My code: 710.0
JGraphT: 708.0 - My code: 708.0
JGraphT: 623.0 - My code: 623.0
JGraphT: 532.0 - My code: 532.0
JGraphT: 477.0 - My code: 477.0
JGraphT: 763.0 - My code: 763.0
JGraphT: 776.0 - My code: 776.0
JGraphT: 782.0 - My code: 782.0
JGraphT: 698.0 - My code: 698.0
JGraphT: 611.0 - My code: 611.0
JGraphT: 770.0 - My code: 770.0
JGraphT: 663.0 - My code: 663.0
JGraphT: 628.0 - My code: 628.0
JGraphT: 518.0 - My code: 518.0
JGraphT: 471.0 - My code: 471.0
JGraphT: 444.0 - My code: 444.0
JGraphT: 716.0 - My code: 716.0
JGraphT: 614.0 - My code: 614.0
JGraphT: 527.0 - My code: 527.0
JGraphT: 700.0 - My code: 700.0
JGraphT: 755.0 - My code: 755.0
我不明白为什么结果不同，希望得到解释并可能解决我的问题。预先感谢您。
您的实现中的问题似乎与
predpred这是您的
Dijkstrapublic static ArrayList<double[]> dijkstra(DefaultUndirectedWeightedGraph<String, DefaultWeightedEdge> graph, int source) {
final double inf = Double.POSITIVE_INFINITY;
double[] dist = new double[graph.vertexSet().size()];
int[] pred = new int[graph.vertexSet().size()];
ArrayList<Integer> Q = new ArrayList<Integer>(0);
Set<String> vertexSet = graph.vertexSet();
for (String vString : vertexSet) {
int v = Integer.parseInt(vString);
dist[v] = inf;
pred[v] = -1;
Q.add(v);
}
dist[source] = 0;
while (!Q.isEmpty()) {
int min = Q.get(0);
for (int i : Q) {
if (dist[i] < dist[min]) {
min = i;
}
}
int u = min;
Q.remove(Integer.valueOf(u));
Set<DefaultWeightedEdge> edges = graph.edgesOf(Integer.toString(u));
for (DefaultWeightedEdge edge : edges) {
int v = Integer.parseInt(graph.getEdgeTarget(edge));
double alt = dist[u] + graph.getEdgeWeight(edge);
if (alt < dist[v]) {
dist[v] = alt;
pred[v] = u;
}
}
}
ArrayList<double[]> returnData = new ArrayList<double[]>(0);
returnData.add(dist);
returnData.add(Arrays.stream(pred).asDoubleStream().toArray());
return returnData;}
主要变化：
predint[]predArrays.stream(pred).asDoubleStream().toArray()请注意，这个更正后的版本应该更符合 Dijkstra 算法中前驱数组的预期用途。另外，在将结果与 JGraphT 进行比较时，请记住，浮点比较有时会因精度问题而导致较小的差异，因此，如有必要，最好使用较小的 epsilon 值进行此类比较。