在加权图中查找从节点到所有其他节点的距离

Question

如何找到并保存图中特定节点到所有其他节点的距离。请注意，该图是非循环的。

这是我开始时使用的代码。我传递了一个顶点、已访问数组、两个节点之间的距离矩阵，该矩阵最初设置为 0，
和 dist 应该跟踪当前节点与
我给出的根节点的距离目标。
我使用 DFS，每次我转到下一个节点时，我都会将它们之间的距离添加到先前的
距离，并将其作为参数传递给下一个连接（如果存在）。
请帮我完成。

 void DFSUtil(int v,boolean visited[],ArrayList<ArrayList<Integer>> distanceMatrix,int dist,int targ)
    {
        // Mark the current node as visited and print it
        visited[v]=true;
        System.out.print(v+" ");


        // Recur for all the vertices adjacent to this vertex
        Iterator<Integer> i = adj[v].listIterator();

        while (i.hasNext())
        {
            int n = i.next();

            if (!visited[n]){
                /* dist += distanceMatrix.get(v).get(n);
                System.out.println("cur:"+v+" next:"+n+"\ndistMatrix:"+distanceMatrix.get(v).get(n)+"dist:"+dist);

                distanceMatrix.get(targ).set(n,dist);
                distanceMatrix.get(n).set(targ,dist);
                System.out.println(distanceMatrix);
                System.out.println();*/
                DFSUtil(n, visited,distanceMatrix,dist,targ);
            }
        }
        //remove dist from root to this node
    }

Answer 1

如果您正在寻找全对最短路径问题，您可以使用 Floyd-Warshall Algorithm。

Answer 2

我假设你指的是有向无环图。可以使用在 O(E + VlogV) 中运行的 Dijkstra's。

Answer 3

您不需要 djikstras，因为该图是非循环的。相反，拓扑排序可用于 |V + E| 的运行时间。

在加权图中查找从节点到所有其他节点的距离

Find distance from node to all other nodes in a weighted graph

algorithm

graph

nodes

depth-first-search