Dijkstra无向图的最短路径 [英] Dijkstra shortest path for an undirected graph

问题描述

我的下面的代码对于有向图很好地工作，当给定一个无向图时，它不会返回最短路径。

  public void Djikstra（int s）{
 boolean [] marked = new boolean [V]; 
 dist = new double [V]; 
 
 for（int i = 0; i  dist [i] = Double.POSITIVE_INFINITY; 
} 
 dist [s] = 0.0; 
 
队列<整数> pqs =新的PriorityQueue< Integer>（）; 
 
 pqs.add（s）; 
 while（！pqs.isEmpty（））{
 int v = pqs.poll（）; 
 
 if（标记[v]）继续; 
标记[v] = true; 
 
 for（Edge e：get_list（v））{＃get_list（v）将从索引v 
v = e.getV（）
中的邻接列表返回一个迭代w = e.getW（）; （b）如果（dist [w]> dist [v] + e.getWeight（））{
 dist [w] = dist [v] + e.getWeight（）; 
距离[w] = e #all距离将存储在这个数组中
 pqs.add（w）; 
} 
} 
} 
} 
  

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无向图的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！