Implementazione dell'algoritmo di Dijkstra che fornisce risultati errati

Question

Ho bisogno di aiuto nell'implementazione dell'algoritmo di Dijkstra e speravo che qualcuno potesse aiutarmi. Ce l'ho in modo che stia stampando alcuni dei percorsi ma non sta catturando i costi corretti per il percorso.

Qui è la mia struttura del nodo:

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

    } 

Ecco il mio algoritmo:

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

Questo è ciò che il grafico si presenta come:

Il nodo lista grafico è essenzialmente

Node - nodi vicini

Così, per esempio:

Node = Olympia, nodi vicini = Lacey e Tacoma

Answer 1

avevo bisogno di riscrivere l'intero algoritmo in quanto non stava elaborando correttamente:

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

Credo che il problema è che

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

Si esegue un assegnamento diretto di co st, invece di un'aggiunta di vecchi e nuovi costi.

Inoltre, il fatto che si fa

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

direttamente prima che significa che se il costo del percorso è l'infinito, si fa l'esatto contrario - si aggiungono a zero al costo del percorso, rendendolo il meno costoso invece del percorso più costoso.

Se si desidera verificare correttamente l'infinito, è necessario saltare a titolo definitivo seguendo tale percorso quando si ispeziona il suo costo, non solo saltare il calcolo del costo.