Implémentation de l'algorithme de Dijkstra donnant des résultats incorrects

Question

J'ai besoin d'aide pour implémenter l'algorithme de Dijkstra et j'espérais que quelqu'un puisse m'aider. Je l'ai pour qu'il imprime certaines routes mais il ne capture pas les coûts corrects pour le chemin.

Voici ma structure de noeud:

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

    } 

Voici mon algorithme:

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

C'est ce que le graphique ressemble à:

Le nœud de la liste graphique est essentiellement

Noeud - nœuds voisins

Ainsi, par exemple:

noeud = Olympia, noeuds voisins = Lacey et Tacoma

Answer 1

je devais réécrire l'algorithme entier comme il n'a pas été correctement le traitement:

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

Je pense que le problème est que

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

Vous faites une affectation directe de co st, au lieu d'un ajout de coûts anciens et nouveaux.

En outre, le fait que vous faites

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

directement avant cela signifie que si le coût du chemin est infini, vous faites le contraire - vous ajoutez zéro au coût du chemin, ce qui en fait le chemin le moins cher au lieu du plus cher.

Si vous voulez vérifier l'infini correctement, vous devez carrément ignorer ce chemin lorsque vous en analysez le coût, et pas seulement calculer le coût.