获得从节点到自身的最短路径的算法 -- 邻接矩阵 -- 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 的最短路径应该 return 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;

Answer 2

网格中两个节点之间的最短路径可以用Manhattan distance

来描述

Manhattan distance:
The distance between two points in a grid based on a strictly horizontal and/or vertical path (that is, along the grid lines), as opposed to the diagonal or "as the crow flies" distance. The Manhattan distance is the simple sum of the horizontal and vertical components, whereas the diagonal distance might be computed by applying the Pythagorean theorem.
Source

现在，如果您希望将此应用于查找最短路径，您应该阅读 Heuristics and more specifically the A* Algorithm。

也许这个问题和答案对你有用：A* Algorithm with Manhattan Distance Heuristic

Answer 3

运行 Dijkstra 为每个起始节点计算所有对最短路径。然后，您可以通过遍历相邻节点并添加此边权重来计算自最短路径。在某些情况下，最短路径将是无穷大，具体取决于节点的入度。

Answer 4

这是一种寻找从一个节点到自身的最短路径的棘手方法具有非负权重的有向图，将那个节点（比如s）分成两个节点s和s'，额外的一个s'被认为是一个虚拟的，如果s有自循环，则建立具有相同权重的双向边，并复制所有涉及 s 和 s' 的边，即用 s' 替换 s。那么问题就变成了寻找从s'到s的最短路径。你只需要稍微修改一下 Dijkstra 的算法就可以实现这个想法。只需更改初始化。不是设置 d[s]=0 并且所有其他的都是无穷大，而是为 s.

的每个相邻节点设置 d[u] = w(s,u)

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

Algorithm to get shortest path from node to itself -- Adjacency Matrix -- Java

java

algorithm

directed-graph

dijkstra

adjacency-matrix