获取从节点到自身的最短路径的算法——邻接矩阵——Java

Question

public int dijkstra(){
    boolean[] visited = new boolean[gSize];

    int src = 1;
    int dest = 1;
    int[] distance = new int[5];
    int[] part = new int[5];
    int min;
    int nextNode = 0;

    for(int i = 0; i < 5; i++)
    {
        visited[i] = false;
        part[i] = 0;

        for(int j = 0; j < 5; j++)
            if(arr[i][j] == -1)
                arr[i][j] = 999; //gives it a high value to ignore
    }

    distance = arr[src];
    distance[src] = 0;

    visited[src] = true;

    for(int i = 0; i < 5; i++)
    {
        min = 999;

        for(int j = 0; j < 5; j++)
            if(min > distance[j] && visited[j] != true)
            {
                min = distance[j];
                nextNode = j;
            }

        visited[nextNode] = true;

        for(int k = 0; k < 5; k++)
            if(visited[k] != true)
                if(min + arr[nextNode][k] < distance[k])
                {
                    distance[k] = min + arr[nextNode][k];
                    part[k] = nextNode;
                }
    }
    return distance[dest];
}

这个 Dijkstra 算法按预期工作。但是，它仅适用于从顶点“x”到顶点“y”。我一生都无法弄清楚如何找到从顶点“x”到顶点“x”的最短路径。

例如：

从 B 到 B 的最短路径应返回 9 (B -> C -> E -> B)。我是否认为 Dijkstra 算法可以解决这个问题，采取了错误的方法？谢谢你！

Answer 1

您可以搜索从与 x 相邻的节点开始到节点 x 结束的最短路径。

最短路径是从 x 到相邻节点的路径长度加上从该相邻节点到 x 的最短路径长度的最短总和。

基本上是伪代码：

// Note: The function neighbors(x) returns the list of neighbors of node x
// The function distance(x, y) returns distance between node x and y
// applying dijkstra algorithm

shortestDistance = 0;
for (Node neighbor : neighbors(x)) {
   currentDistance = distance(x, neighbor) + distance(neighbor, x);
   shortestDistance = min(currentDistance, shortestDistance);
}
return shortestDistance;