2

我试图从维基百科页面上的伪代码中实现 Dijkstra 的算法。在轮询队列后，我设置了一个条件，测试当前节点是否是目标节点，b。如果是这样，那么算法将中断并返回从 a 到 b 的路径。

这个条件总是会得到满足，因为我知道邻接矩阵范围内的所有节点确实存在。该程序旨在模拟伦敦地铁地图的连接。

无论如何，我一直试图弄清楚这一点，但到目前为止它还没有解决。也许有人可以发现问题。哦，adj这只是我的图的邻接矩阵。

    /**
   Implementation of Dijkstra's Algorithm taken from "Introduction to 
   Algorithms" by Cormen, Leiserson, Rivest and Stein. Third edition.

   d = Array of all distances.
   pi = Previous vertices.
   S = Set of vertices whose final shortest path weights have been
   determined.
   Q = Priority queue of vertices.
**/
public ArrayList<Integer> dijkstra(Integer a, Integer b){
    final double[] d = new double[adj.length];
    int[] pi = new int[adj.length];
    HashSet<Integer> S = new HashSet<Integer>();
    PriorityQueue<Integer> Q = new PriorityQueue<Integer>(d.length, new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                Double dblA = d[a-1];
                Double dblB = d[b-1];
                return dblA.compareTo(dblB);
            }
        });

    for(int i=0; i<d.length; i++){
        d[i] = Double.POSITIVE_INFINITY;
    }
    d[a] = 0f;
    for(int i=0; i<d.length; i++){
        Q.add(i+1);
    }

    while(Q.size() > 0){
        int u = Q.poll();
        if(u == b){
            System.out.println("jjd");
            ArrayList<Integer> path = new ArrayList<Integer>();
            for(int i=pi.length-1; i>=0; i--){
                path.add(pi[i]);
            }
            return path;
        }
        S.add(u);

        if(d[u] == Double.POSITIVE_INFINITY){
            break;
        }

        for(int v=0; v<adj.length; v++){
            double tmp = d[u] + adj[u][v];
            if(tmp < d[v]){
                d[v] = tmp;
                pi[v] = u;
            }
        }
    }
    return new ArrayList<Integer>();
}

}

编辑：- 在做了一些调试之后，似乎 while 循环的主体只执行了一次。

4

2 回答 2

2 
    if(d[u] == Double.POSITIVE_INFINITY){
        break;
    }

    for(int v=0; v<adj.length; v++){
        double tmp = d[u] + adj[u][v];
        if(tmp < d[v]){
            d[v] = tmp;
            pi[v] = u;
        }
    }

循环体中值的更改d不会重新排列优先级队列，因此除非在弹出初始节点后恰好位于队列顶部的元素是其邻居之一，否则您将d[u] == Double.POSITIVE_INFINITY在下一次迭代中拥有并且那就休息吧。

在 Dijkstra 算法中，重要的是当节点的距离发生变化时更新队列。java.util.PriorityQueue<E>不提供该功能，因此使用它并非易事，除了在每次更新时删除和重新添加更新的节点外，我认为没有其他方法可以使用它。这当然不是很有效，因为移除是O(size).

可以通过不让所有节点都在队列中来减轻效率低下。星号仅添加初始节点，并在循环中仅插入尚未看到的邻居，删除并重新插入已经在队列中的邻居。这样可以缩短队列，并且平均而言使移除成本更低。

为了实现高效，您需要一个自定义优先级队列，以允许更快（O(log size)？）更新优先级。

于 2012-11-19T22:18:54.493 回答
0

如果您在从 System.out.println 运行程序时在控制台中输出“jjd”，您的问题应该是这样的：

         if(u == b){
            System.out.println("jjd");
            ArrayList<Integer> path = new ArrayList<Integer>();
            for(int i=pi.length-1; i>=0; i--){
                path.add(pi[i]);
            }
            return path;

当您调用“返回路径”时；您实际上破坏了整个方法并返回“路径”。

于 2012-11-19T22:03:59.470 回答