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

这是图的样子：

图形列表节点本质上是

个

节点 - 邻居节点

因此，例如：

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

Answer 1

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

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

Answer 2

我认为这个问题是

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

您直接转让co st，而不是增加新旧成本。

而且，你做

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

直接之前其实就意味着，如果路径的成本是无穷大，你做的正好相反 - 你加零到的成本路径，使其成本最低，而不是最昂贵的路径。

如果您想正确检查无穷大，您必须在检查其成本时直接跳过该路径，而不是跳过计算成本。