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();
        }
    }

这是图表的样子： 图表列表节点基本上是：

节点 -- 相邻节点

例如：

节点 = 奥林匹亚，相邻节点 = 莱西和塔科马

- Yecats

---

为了减少缩进的数量，您可以倒置if语句并使用continue跳转到下一个i。例如：if (_algorithmList[i].Name.Name != neighbor.Name.Name) continue; - Daniel Imms

Answer 1

我认为问题在于

_cost = _algorithmList[j].Cost; //将成本设置为父级成本

你直接赋值了成本，而不是将旧成本和新成本相加。

此外，你在这之前直接进行了判断：

if (_algorithmList[j].Cost != 100000000) //不是无穷大

这意味着如果路径的成本是无穷大，你会做相反的事情 - 你将零添加到路径的成本中，使它成为最便宜的路径，而不是最昂贵的路径。

如果你想正确地检查无穷大，你必须直接跳过检查其成本的路径，而不仅仅是跳过计算成本。

- Patashu

---

我不是完全明白。对于第一个参考（_cost assignment）- 我将邻居节点的成本加到下面父节点的成本上。我的思路是这就是成本应该是什么...父节点+当前节点...理论上父节点会有总成本。对于第二个参考，那是为了检查节点是否已经被查看过了（也就是说，已经找到了一个父节点）。很抱歉，我不太明白如何改进我的代码使其正常工作。请澄清一下！谢谢 :) - Yecats

@Yecats 好的，你的算法可能有更微妙的错误...请稍等，我再仔细检查一遍 XD 同时，也许可以使用调试器/穷人版调试器来查看它是否有任何可疑的问题？你还可以在一个非常简单的图形上进行测试，比如只有3-4个边。 - Patashu

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);
        }
    }

- Yecats