Advertisement
awsmpshk

Dijkstra

Dec 12th, 2021
596
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public Dictionary<T, long> Dijkstra(T node)
  2.         {
  3.             ClearVisited();
  4.             _visited[node] = true;
  5.             var currentNode = _adjacencyList[node];
  6.            
  7.             InstantiateAllNodesList();
  8.             foreach (var item in _allNodes)
  9.             {
  10.                 if (!currentNode.ContainsKey(item))
  11.                 {
  12.                     currentNode.Add(item, Int32.MaxValue);
  13.                 }
  14.             }
  15.  
  16.             Dictionary<T, long> dists = new Dictionary<T, long>();
  17.  
  18.             for (int i = 0; i < _allNodes.Count; ++i)
  19.             {
  20.                 dists.Add(_allNodes[i], currentNode[_allNodes[i]]);
  21.             }
  22.  
  23.             foreach (var item in currentNode)
  24.             {
  25.                 Console.WriteLine($"{item.Key.ToString()} --- {item.Value}");
  26.             }
  27.            
  28.             foreach (var element in _allNodes)
  29.             {
  30.                 long min = Int32.MaxValue;
  31.                 T w = _allNodes[0];
  32.  
  33.                 foreach (var nextElement in _allNodes)
  34.                 {
  35.                     if (!_visited[nextElement] && dists[nextElement] < min)
  36.                     {
  37.                         min = dists[nextElement];
  38.                         w = nextElement;
  39.                     }
  40.                 }
  41.  
  42.                 _visited[w] = true;
  43.  
  44.                 foreach (var nextElement in _allNodes)
  45.                 {
  46.                     long dist = dists[w] + this[w, nextElement];
  47.  
  48.                     if (!_visited[nextElement] && dist < dists[nextElement])
  49.                     {
  50.                         dists[nextElement] = dist;
  51.                     }
  52.                 }
  53.             }
  54.  
  55.             return dists;
  56.         }
Advertisement
RAW Paste Data Copied
Advertisement