Dijkstra无向图的最短路径

我的下面的代码对于有向图非常适用，当给定无向图时，它不会返回最短路径。

public void Djikstra(int s){ boolean[] marked = new boolean[V]; dist = new double[V]; for(int i = 0; i<V; i++){ # initializing array dist[i] = Double.POSITIVE_INFINITY; } dist[s] = 0.0; Queue pqs = new PriorityQueue(); pqs.add(s); while(!pqs.isEmpty()){ int v = pqs.poll(); if(marked[v]) continue; marked[v] = true; for(Edge e : get_list(v)){ # get_list(v) will return an iterable from the adjacency list at index vv = e.getV() int w = e.getW(); if(dist[w] > dist[v] + e.getWeight()){ dist[w] = dist[v] + e.getWeight(); distances[w] = e #all the distances will be stored in this array pqs.add(w); } } } } 

我不确定这里的错误是什么？ 我确定这是一个简单的错误，一些提示将完成这项工作。

谢谢。

编辑：

 public void addEdge(Edge e){ adj[e.getV()].add(e); adj[e.getW()].add(e); } 

Answer 1

考虑从节点1到2的有向路径与从节点1到2的无向路径之间的差异。

您需要将哪些内容添加到有向图（您的算法可以解决）以使其等效于无向图？

编辑：

我想，想出来了。 以下是提示：您正在更改for循环中的重置v。 这不会导致有向图的错误，但是如果边缘被列为从w到v而不是v到w无向，会发生什么？

EDIT2：

像这样的东西：

首先，删除v = e.getV();

第二，将下一行更改为int w = (v == e.getV()) ? e.getW() : e.getV(); int w = (v == e.getV()) ? e.getW() : e.getV();

这会将w的值设置为边v的哪个顶点不是。

第二个建议等同于以下内容（可能更容易阅读）：

 int w = e.getW(); if (w == v) { w = e.getV(); } 

Answer 2

您必须添加两个不同的边，直接和反向。 更改

 public void addEdge(Edge e){ adj[e.getV()].add(e); adj[e.getW()].add(e); } 

在

 public void addEdge(Edge e){ adj[e.getV()].add(e); } 

并且，当您添加边时，请执行以下操作：

 Edge e = new Edge(from, to, weight); Edge f = new Edge(to, from, weight); addEdge(e); addEdge(f);