Dijkstra 算法：如果有 2 个未连接的图，它应该工作吗？

Question

我目前已经实现了 Dijkstra 的算法，但是当我用这样的图测试我的算法时出现了问题：

并尝试从 C 转到 B。我知道为什么它不起作用。但是我想知道如果有这样的图表，正常的实现是否可行？

  internal static Stack<string> Dijkstra(string sourcePoint, string targetPoint, Graph graph)
    {
        List<string> verticesStringList = graph.GetAllVertices();
        Dictionary<string, Vertex> verticesDictionary = new Dictionary<string, Vertex>();
        InitializeVerticesDictionary(sourcePoint, verticesStringList, verticesDictionary);

        while (verticesDictionary.Values.ToList().Any(x => x.IsVisited == false))
        {
            KeyValuePair<string, Vertex> keyValuePair = verticesDictionary.Where(x => x.Value.IsVisited == false).ToList().Min();
            string vertexKey = keyValuePair.Key;
            Vertex currentVertex = keyValuePair.Value;
            List<string> neighbourVertices = graph.GetNeighbourVerticesSorted(keyValuePair.Key);
            foreach (string neighbourVertexString in neighbourVertices)
            {
                Vertex neighbourVertex = verticesDictionary[neighbourVertexString];
                int newDistanceFromStartVertex = currentVertex.ShortestDistanceFromTarget + graph.GetEdgeWeight(keyValuePair.Key, neighbourVertexString);
                if (newDistanceFromStartVertex < neighbourVertex.ShortestDistanceFromTarget)
                {
                    verticesDictionary[neighbourVertexString].ShortestDistanceFromTarget = newDistanceFromStartVertex;
                    verticesDictionary[neighbourVertexString].PreviousVertex = keyValuePair.Key;
                }
            }
            verticesDictionary[vertexKey].IsVisited = true;
        }

        return FormShortestPath(targetPoint, verticesDictionary);

    }

    private static Stack<string> FormShortestPath(string targetPoint, Dictionary<string, Vertex> verticesDictionary)
    {
        Stack<string> traverseStack = new Stack<string>();
        KeyValuePair<string, Vertex> vertex = verticesDictionary.Where(x => x.Key == targetPoint).FirstOrDefault();
        while (vertex.Value.PreviousVertex != null)
        {
            traverseStack.Push(vertex.Value.PreviousVertex + " Goes To " + vertex.Key); //the end edge
            vertex = verticesDictionary.Where(x => x.Key == vertex.Value.PreviousVertex).FirstOrDefault();
        }
        return traverseStack;
    }



private static void InitializeVerticesDictionary(string sourcePoint, List<string> verticesStringList, Dictionary<string, Vertex> verticesDictionary)
    {
        foreach (string vertexString in verticesStringList)
        {
            Vertex vertex = new Vertex
            {
                ShortestDistanceFromTarget = int.MaxValue
            };

            if (vertexString == sourcePoint)
            {
                vertex.ShortestDistanceFromTarget = 0;
            }

            verticesDictionary.Add(vertexString, vertex);
        }
    }

更新：我将条件更改为 verticesDictionary.Values.ToList().Any(x => x.IsVisited == false && x.ShortestDistanceFromTarget != int.MaxValue)，现在我没有收到评论中提到的溢出。

Answer 1

IsVisited 这里有点误导，因为您实际上可以访问您无法从源节点到达的节点。我会将其重命名为 isProcessed。要检查您是否可以从源节点到达另一个节点，您需要检查它的距离是否为 int.maxVal.

为避免溢出，当currentVertex.ShortestDistanceFromTarget为int.maxVal时不要迭代邻居，因为它已经是源节点无法访问的节点。

Dijkstra 算法：如果有 2 个未连接的图，它应该工作吗？

Dijkstra algorithm: should it work if there are 2 graphs that are not connected?

c#

algorithm

graph

dijkstra

graph-algorithm