c# - Dijkstra 的算法实现给出了不正确的结果

Question

我需要一些帮助来实施 Dijkstra 算法，并希望有人能够帮助我。我有它，以便它打印一些路线，但它没有捕获路径的正确成本。

这是我的节点结构：

   class Node
    {
        public enum Color {White, Gray, Black};
        public string Name { get; set; } //city
        public List<NeighborNode> Neighbors { get; set; } //Connected Edges
        public Color nodeColor = Color.White;
        public int timeDiscover { get; set; }//discover time
        public int timeFinish { get; set; } // finish time

        public Node() 
        { 
            Neighbors = new List<NeighborNode>();
        }
        public Node(string n, int discover)
        {
            Neighbors = new List<NeighborNode>();
            this.Name = n;
            timeDiscover = discover;
        }


        public Node(string n, NeighborNode e, decimal m)
        {
            Neighbors = new List<NeighborNode>();
            this.Name = n;
            this.Neighbors.Add(e);
        }

    }

    class NeighborNode
    {
        public Node Name { get; set; }
        public decimal Miles { get; set; } //Track the miles on the neighbor node

        public NeighborNode() { }
        public NeighborNode(Node n, decimal m)
        {
            Name = n;
            Miles = m;
        }

    }

这是我的算法：

   public void DijkstraAlgorithm(List<Node> graph)
    {

        List<DA> _algorithmList = new List<DA>(); //track the node cost/positioning
        Stack<Node> _allCities = new Stack<Node>(); // add all cities into this for examination
        Node _nodeToExamine = new Node(); //this is the node we're currently looking at.
        decimal _cost = 0;

        foreach (var city in graph) // putting these onto a stack for easy manipulation. Probably could have just made this a stack to start
        {
            _allCities.Push(city);
            _algorithmList.Add(new DA(city));
        }

        _nodeToExamine = _allCities.Pop(); //pop off the first node

        while (_allCities.Count != 0) // loop through each city
        {

            foreach (var neighbor in _nodeToExamine.Neighbors) //loop through each neighbor of the node
            {
                for (int i = 0; i < _algorithmList.Count; i++) //search the alorithm list for the current neighbor node
                {
                    if (_algorithmList[i].Name.Name == neighbor.Name.Name) //found it
                    {
                        for (int j = 0; j < _algorithmList.Count; j++) //check for the cost of the parent node
                        {
                            if (_algorithmList[j].Name.Name == _nodeToExamine.Name) //looping through
                            {
                                if (_algorithmList[j].Cost != 100000000) //not infinity
                                    _cost = _algorithmList[j].Cost; //set the cost to be the parent cost

                                break;
                            }
                        }
                        _cost = _cost + neighbor.Miles;

                        if (_algorithmList[i].Cost > _cost) // check to make sure the miles are less (better path)
                        {
                            _algorithmList[i].Parent = _nodeToExamine; //set the parent to be the top node
                            _algorithmList[i].Cost = _cost; // set the weight to be correct
                            break;
                        }
                    }
                }

            }
            _cost = 0;
            _nodeToExamine = _allCities.Pop();
        }
    }

这是图表的样子：

图列表节点本质上是

节点——相邻节点

例如：

节点 = Olympia，相邻节点 = Lacey 和 Tacoma

Answer 1

我认为问题在于

_cost = _algorithmList[j].Cost; //set the cost to be the parent cost

您直接分配成本，而不是添加新旧成本。

此外，你这样做的事实

if (_algorithmList[j].Cost != 100000000) //not infinity

直接在它之前意味着如果路径的成本是无穷大的，那么你会做相反的事情 - 你将路径的成本加为零，使其成为最便宜的路径而不是最昂贵的路径。

如果要正确检查无穷大，则必须在检查其成本时完全跳过该路径，而不仅仅是跳过计算成本。

Answer 2

我需要重写整个算法，因为它没有正确处理：

    public void DijkstraAlgorithm(List<Node> graph)
    {

        List<DA> _algorithmList = new List<DA>(); //track the node cost/positioning
        DA _nodeToExamine = new DA(); //this is the node we're currently looking at.
        bool flag = true; //for exting the while loop later

        foreach (var node in graph)
        {
            _algorithmList.Add(new DA(node));
        }

        foreach (var children in _algorithmList[0].Name.Neighbors) //just starting at the first node
        {
            for (int i = 0; i < _algorithmList.Count; i++)
            {
                if (children.Name == _algorithmList[i].Name)
                {
                    _algorithmList[i].Parent = _algorithmList[0].Name;
                    _algorithmList[i].Cost = children.Miles;
                    _algorithmList[0].Complete = true;

                }
            }
        }

        while (flag) //loop through the rest to organize
        {
            _algorithmList = _algorithmList.OrderBy(x => x.Cost).ToList(); //sort by shortest path

            for (int i = 0; i < _algorithmList.Count; i++) //loop through each looking for a node that isn't complete
            {
                if (_algorithmList[i].Complete == false)
                {
                    _nodeToExamine = _algorithmList[i];
                    break;
                }
                if (i == 13) //if the counter reaches 13 then we have completed all nodes and should bail out of the loop
                    flag = false;
            }
            if (_nodeToExamine.Name.Neighbors.Count == 0) //set any nodes that do not have children to be complete
            {
                _nodeToExamine.Complete = true;
            }

            foreach (var children in _nodeToExamine.Name.Neighbors) //loop through the children/neighbors to see if there's one with a shorter path
            {
                for (int i = 0; i < _algorithmList.Count; i++) 
                {
                    if (children.Name == _algorithmList[i].Name)
                    {
                        if (_nodeToExamine.Cost + children.Miles < _algorithmList[i].Cost) //found a better path
                        {
                            _algorithmList[i].Parent = _nodeToExamine.Name;
                            _algorithmList[i].Cost = _nodeToExamine.Cost + children.Miles;
                        }
                    }
                }
                _nodeToExamine.Complete = true;
            }
        }

        PrintDijkstraAlgoirthm(_algorithmList);
    }


    public void PrintDijkstraAlgoirthm(List<DA> _finalList)
    {
        foreach (var item in _finalList)
        {
           if (item.Parent != null)
                Console.WriteLine("{0} ---> {1}: {2}", item.Parent.Name, item.Name.Name, item.Cost);
        }
    }