我的下面的代码对于有向图很好地工作，当给定一个无向图时，它不会返回最短路径。
public void Djikstra（int s）{ boolean [] marked = new boolean [V]; dist = new double [V]; for（int i = 0; i谢谢。
编辑：
public void addEdge（Edge e）{ adj [e.getV（）]。add（e ）; adj [e.getW（）]。add（e）;解决方案
从节点1到2的路径以及从节点1到2的无向路径。
您需要添加到有向图（您的算法可以解决的问题）它相当于无向图吗？
编辑：
我想。以下是提示：您目前正在更改for循环中的重置v。这不会导致一个有向图的错误，但是如果边被列为从w到v而不是v到w不定向会发生什么？
EDIT2：
类似这样：
首先，移除 v = e.getV（）;
其次，将下一行更改为 int w =（v == e.getV（））？ e.getW（）：e.getV（）;
这将w的值设置为边v的哪个顶点不是。
第二个建议等同于以下内容（可能更容易阅读）：
int w = e.getW（）; if（w == v）{ w = e.getV（）; }
My following code is working perfectly fine for directed graphs and when given an undirected graph, it will not return the shortest path.
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<Integer> pqs = new PriorityQueue<Integer>(); 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 v v = 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); } } } }I'm not sure what's my mistake over here? I'm kind of sure it's a simple error, some hints will do the job.
Thanks.
Edit:
public void addEdge(Edge e){ adj[e.getV()].add(e); adj[e.getW()].add(e); }解决方案
Consider the differences between a directed path from node 1 to 2 and an undirected path from node 1 to 2.
What would you need to add to the directed graph (which your algorithm can solve) to make it equivalent to the undirected graph?
EDIT:
Figured it out, I think. Here's the hint: You are currently changing resetting v inside of your for loop. This will not cause an error with a directed graph, but what happens if the edge is listed as going from w to v instead of v to w undirected?
EDIT2:
Something like this:
First, remove v = e.getV();
Second, change the next line to int w = (v == e.getV()) ? e.getW() : e.getV();
This sets the value of w to whichever vertex of your edge v is NOT.
This second suggestion is equivalent to the following (maybe a bit easier to read):
int w = e.getW(); if (w == v) { w = e.getV(); }
更多推荐
Dijkstra无向图的最短路径
发布评论