0

给定一个邻接矩阵，我需要计算第一个顶点和最后一个顶点之间的最短路径（通常是顶点 i 和 j，但我们暂时可以忽略它）。我编写了一个算法，它实际上只能正确计算第一个节点和第二个节点之间的距离（我猜是朝着正确方向迈出的一步）。

static int dijkstra(int[][] G, int i, int j) {
    //Get the number of vertices in G
    int n = G.length;
    int[] bestpath = new int[n];
    int max = Integer.MAX_VALUE;
    boolean[] visited = new boolean[n];

    for (int x = 0; x < n; x++) {
        visited[x] = false;
        bestpath[x] = max;
    }

    bestpath[i] = 0;

    for (int x = 0; x < n; x++) {
        int min = max;
        int currentNode = i;
        for (int y = 0; y < n; y++) {
            if (!visited[y] && bestpath[y] < min) {
                System.out.println(G[y][x]);
                currentNode = y;
                min = bestpath[y];
            }
        }
        visited[currentNode] = true;
        for (int y = 0; y < n; y++) {
            if (G[currentNode][y] < max && bestpath[currentNode] + G[currentNode][y] < bestpath[y]) {
                bestpath[y] = bestpath[currentNode] + G[currentNode][y];
            }
        }
    }

    return bestpath[j];
}

如果我猜的话，我会说我的逻辑在本节中有缺陷：

 for (int y = 0; y < n; y++) {
            if (!visited[y] && bestpath[y] < min) {
                System.out.println(G[y][x]);
                currentNode = y;
                min = bestpath[y];
            }
 }

一个例子是矩阵

0 1 0 
1 0 1
0 1 0

这将返回 2（在权重 1 的顶点 1 和顶点 2 之间的一条路径，以及权重为 1 的 2 和 3 之间的另一条路径）。

4

1 回答 1

0

如果矩阵不仅存储 1 和 0，还存储 i 到 j 的距离，那么您确实需要跟踪从任何节点 i 到 j 的最佳距离。换句话说，您的工作数组应该是一个工作矩阵。即使你只是做一个非加权图，我认为这种方法更好。

SPF算法有不同的版本。为您尝试翻译成 java 的内容发布伪代码。

于 2012-12-03T02:52:51.133 回答