c# - c#中的Dijkstras算法

Question

从头开始构建使用 Dijkstras alg 的图表控件。我搜索了互联网试图理解这个算法。我想我终于明白了，但我的代码无法正常工作。希望有人可以看看这个，看看他们是否知道这是怎么回事......

我将粘贴三种方法，因为我认为这是可能需要的一切。

对于初学者，我会说我创建了自己的 Vertex 数据类型。它包含节点的 ID、X 和 Y、状态字符串、也是顶点数据类型的父节点和整数距离。

    //function to populate lists with all the vertices on the graph
    private List<Vertex> getNodes()
    {
        myVertices.Clear();
        //get all non-dg nodes in list
        for (int i = 0; i < chtGraph.Series[0].Points.Count; i++)
        {
            Vertex vertice = new Vertex(chtGraph.Series[0].Points[i]["ID"], (float)chtGraph.Series[0].Points[i].XValue, (float)chtGraph.Series[0].Points[i].YValues[0], "UNVISITED", Convert.ToInt32(chtGraph.Series[0].Points[i].Label), double.PositiveInfinity, null);
            myVertices.Insert(i, vertice);
        }

        //get all dg nodes in list
        for (int i = 0; i < chtGraph.Series[1].Points.Count; i++)
        {
            Vertex vertice = new Vertex(chtGraph.Series[1].Points[i]["ID"], (float)chtGraph.Series[1].Points[i].XValue, (float)chtGraph.Series[1].Points[i].YValues[0], "UNVISITED", Convert.ToInt32(chtGraph.Series[1].Points[i].Label), double.PositiveInfinity, null);
            myVertices.Insert(i, vertice);
        }
        return myVertices;
    }

    //function to return to a list all the adjacents for a specified node.  Excludes parent node
    private List<Vertex> checkAdjacents(Vertex node, int intTransPower)
    {
        List<Vertex> Adjacents = new List<Vertex>();
        int distance;

        for (int i = 0; i < myVertices.Count; i++)
        {
            if (node.id != myVertices[i].id)
            {
                distance = calcDistance(node.x, node.y, myVertices[i].x, myVertices[i].y);

                if (distance <= intTransPower)
                {
                    if (rdbTotalLength.Checked)
                    {
                        myVertices[i].distance = distance;
                    }
                    else if (rdbPathEnergy.Checked)
                    {
                        myVertices[i].distance = getCost(node, myVertices[i]);
                    }
                    else
                    {
                        myVertices[i].distance = 1;
                    }

                    myVertices[i].parent = node;
                    Adjacents.Add(myVertices[i]);

                    foreach (Vertex p in openList)
                    {
                        if (myVertices[i].id == p.id)
                        {
                            p.distance = myVertices[i].distance;
                            p.parent = myVertices[i].parent;
                        }
                    }
                }
            }
        }

        return Adjacents;

    }

这是dijkstras....目前无法正常工作，我只是想不通。

private void dijkstra(Vertex start, Vertex end)
    {

        openList.Clear();

        //populate two lists with all the nodes in the graph
        openList = getNodes();
        myVertices = getNodes();

        //adjacents list for each vertex visited
        List<Vertex> adjacents = new List<Vertex>();

        //final list that is populated with the final path of vertices
        List<Edge> shortestPath = new List<Edge>();

        //used in calculating adjacent nodes.  If distance is greater than transpower, then nodes are not connected
        int intTransPower = Convert.ToInt32(txtTransPower.Text);

        //set current vertex as the starting node
        Vertex current = start;

        //set initially to false
        bool pathFound = false;

        //find the starting node from the list of all vertices.  Set it's distance to 0
        foreach (Vertex p in openList)
        {
            if (p.id == current.id)
            {
                p.status = current.status;
                p.distance = 0;
            }
        }
        foreach (Vertex p in myVertices)
        {
            if (p.id == current.id)
            {
                p.status = current.status;
                p.distance = 0;
            }
        }

        //reorder the list to bring the starting node to the first element
        openList = openList.OrderBy(h => h.distance).ToList();

        //openList.Add(current);
        //this.insert(openList, current, true);

        // Repeat while the openlist is not empty and you haven't reached the end
        while (openList.Count > 0)
        {
            //remove node at element 0.  Sorted by smallest distance so it always gets removed first
            current = openList[0];
            openList.RemoveAt(0);

            //if the current node = the ending node, then we have found the path.  Break loop and build the final path.
            if (current.id == end.id)
            {
                pathFound = true;
                break;
            }

            //collect up all the adjacent nodes for the current vertex
            //does NOT include the current vertex we are on
            adjacents = checkAdjacents(current, intTransPower);

            foreach (Vertex v in adjacents)
            {
                float alt =  (float)current.distance + calcDistance(current.x, current.y, v.x, v.y);
                Convert.ToInt32(alt);

                if (alt < v.distance)
                {
                    v.distance = alt;
                    v.parent = current;
                    for (int i = 0; i < openList.Count; i++)
                    {
                        if (v.id == openList[i].id)
                        {
                            openList[i].distance = alt;
                            openList[i].parent = current;
                        }
                    }
                }

            }
            openList = openList.OrderBy(h => h.distance).ToList();
        }

        if (pathFound)
        {
            // collect path
            this.foundPath.Clear();
            Vertex last = current;
            while (current != start && current != null)
            {
                this.foundPath.Add(current);
                if (current.parent == last)
                    break;
                last = current;
                current = current.parent;
            }
            this.foundPath.Add(current);
        }

    }

Answer 1

我有这个方法，但它是更大实现的一部分：

public static IDigraph DijkstrasAlgorithm(IDigraph g, int s)
        {
            //Collect number of vertices
            int num1 = g.NumberOfVertices;

            //create an array for vertices
            Entry[] entryArray1 = new Graphos.Algorithms.Entry[num1];

            //for each vertice create new instance for entry of edges
            for (int num2 = 0; num2 < num1; num2++)
            {
                entryArray1[num2] = new Graphos.Algorithms.Entry(false, 0x7fffffff, 0x7fffffff);
            }
            //set vertice origin with distance 0.
            entryArray1[s].distance = 0;

            //create a list for edges
            PriorityQueue queue1 = new BinaryHeap(g.NumberOfEdges);

            //create initial nodes in edges list
            queue1.Enqueue(new Association(0, g.GetVertex(s)));

            //while list is not empty
            while (!queue1.IsEmpty)
            {
                //creates an association
                Association association1 = (Association)queue1.DequeueMin();

                //attributes the vertice
                IVertex vertex1 = (IVertex)association1.Value;

                //if connection is known
                if (!entryArray1[vertex1.Number].known)
                {
                    //checks as known
                    entryArray1[vertex1.Number].known = true;

                    //foreach edge founded
                    foreach (Edge edge1 in vertex1.EmanatingEdges)
                    {
                        //creates the vertex that is being used
                        IVertex vertex2 = edge1.MateOf(vertex1);

                        //catches the weight since vertice in link
                        int num3 = entryArray1[vertex1.Number].distance + ((int)edge1.Weight);

                        //se o peso da ponte for menor que o peso maximo
                        if (entryArray1[vertex2.Number].distance > num3)
                        {
                            //Peso maximo é atualizado para o peso da ponte
                           entryArray1[vertex2.Number].distance = num3;

                            //Define o vértice vizinho 
                            entryArray1[vertex2.Number].predecessor = vertex1.Number;

                           //adiciona o vértice com seu vizinho e o peso entre eles na lista
                            queue1.Enqueue(new Association(num3, vertex2));
                        }
                    }
                }
            }
            //Á este ponto, todas as associações foram feitas

            //Cria o objeto grafo como uma lista baseado no numero de vertices
            IDigraph digraph1 = new DigraphAsLists(num1);

            //Para cada vértice
            for (int num4 = 0; num4 < num1; num4++)
            {
                //adiciona o vertice da lista no grafo
                digraph1.AddVertex(num4, entryArray1[num4].distance);
            }

            //para cada vertice
            for (int num5 = 0; num5 < num1; num5++)
            {
                //Se não for o ponto de origem
                if (num5 != s)
                {
                    //adiciona a aresta(origem,destino baseado no vizinho)
                    digraph1.AddEdge(num5, entryArray1[num5].predecessor);
                }
            }
            //retorna o grafo
            return digraph1;
        }