使用Dijkstra算法找到最短路线 [英] Finding the shortest route using Dijkstra algorithm

问题描述

我需要找到一个图形的2个顶点之间的最短路径。我有一个矩阵，其中包含所有权重。我该怎么做？目前，我有以下代码：

I need to find the shortest route between 2 vertices of a graph. I have a matrix, which contains all the weights. How can I do it? Currently, I have the following code:

private int[] Dijkstra(int start, int end)
    {
        bool[] done = new bool[8];
        int[] parent = new int[8];
        for (int i = 0; i < parent.Length; i++)
            parent[i] = -1;
        int[] distances = new int[8];
        for (int i = 0; i < distances.Length; i++)
            distances[i] = int.MaxValue;
        distances[start] = 0;
        int current = start;
        while (!done[current])
        {
            done[current] = true;
            for (int i = 0; i < 8; i++)
            {
                if (graph[current, i] != int.MaxValue)
                {
                    int dist = graph[current, i] + distances[current];
                    if (dist < distances[i])
                    {
                        distances[i] = dist;
                        parent[i] = current;
                    }
                }
            }
            int min = int.MaxValue;
            for (int i = 0; i < 8; i++)
            {
                if (distances[i] < min&&!done[i])
                {
                    current = i;
                    min = distances[i];
                }
            }
        }
        return parent;
    }

它有效，但是我不知道如何找到它最短的路线，例如1和3之间的路线，返回的路线类似于1 => 4 => 2 => 3。

预先感谢。

It works, but, however I don't know how to make it find the shortest route between, for example 1 and 3, and return the route like 1=>4=>2=>3.
Thanks in advance.

推荐答案

Djikstra的算法使用父数组来跟踪从头到尾的最短路径。您将从parent [end]开始，然后按照数组的条目进行操作，直到重新开始。

Djikstra's Algorithm uses the parent array to track the shortest path from start to end. You'd start at parent[end] and follow the entries of the array until you got back to start.

某些伪代码：

List<int> shortestPath = new List<int>();
int current = end;
while( current != start ) {
     shortestPath.Add( current );
     current = parent[current];
}

shortestPath.Reverse();

您唯一需要担心的问题是是否传递了起始值和结束值in是适当的值（例如，它们是否实际上代表图形中的顶点）。

Only thing you worry have to worry about with your function is whether or not the start and end values passed in are appropriate values (whether or not they actually represent vertices in your graph, for example ).

这篇关于使用Dijkstra算法找到最短路线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！