1 function Dijkstra(Graph, source): 2  3     dist[source] ← 0          // Distance from source to source 4     prev[source] ← undefined  // Previous node in optimal path initialization 5  6     for each vertex v in Graph:  // Initialization 7         if v ≠ source            // Where v has not yet been removed from Q (unvisited nodes) 8             dist[v] ← infinity   // Unknown distance function from source to v 9             prev[v] ← undefined  // Previous node in optimal path from source10         end if 11         add v to Q               // All nodes initially in Q (unvisited nodes)12     end for13     14     while Q is not empty:15         u ← vertex in Q with min dist[u]  // Source node in first case16         remove u from Q 17         18         for each neighbor v of u:         // where v has not yet been removed from Q.19             alt ← dist[u] + length(u, v)20             if alt < dist[v]:             // A shorter path to v has been found21                 dist[v] ← alt 22                 prev[v] ← u 23             end if24         end for25     end while26 27     return dist[], prev[]28 29 end function

Vertex   Distance from Source0                01                42                123                194                215                116                97                88                14

  1 using System;  2 using System.Collections.Generic;  3 using System.Linq;  4   5 namespace GraphAlgorithmTesting  6 {  7   class Program  8   {  9     static void Main(string[] args) 10     { 11       int[,] graph = new int[9, 9] 12       { 13         {0, 4, 0, 0, 0, 0, 0, 8, 0}, 14         {4, 0, 8, 0, 0, 0, 0, 11, 0}, 15         {0, 8, 0, 7, 0, 4, 0, 0, 2}, 16         {0, 0, 7, 0, 9, 14, 0, 0, 0}, 17         {0, 0, 0, 9, 0, 10, 0, 0, 0}, 18         {0, 0, 4, 0, 10, 0, 2, 0, 0}, 19         {0, 0, 0, 14, 0, 2, 0, 1, 6}, 20         {8, 11, 0, 0, 0, 0, 1, 0, 7}, 21         {0, 0, 2, 0, 0, 0, 6, 7, 0} 22       }; 23  24       Graph g = new Graph(graph.GetLength(0)); 25       for (int i = 0; i < graph.GetLength(0); i++) 26       { 27         for (int j = 0; j < graph.GetLength(1); j++) 28         { 29           if (graph[i, j] > 0) 30             g.AddEdge(i, j, graph[i, j]); 31         } 32       } 33  34       int[] dist = g.Dijkstra(0); 35       Console.WriteLine("Vertex\t\tDistance from Source"); 36       for (int i = 0; i < dist.Length; i++) 37       { 38         Console.WriteLine("{0}\t\t{1}", i, dist[i]); 39       } 40  41       Console.ReadKey(); 42     } 43  44     class Edge 45     { 46       public Edge(int begin, int end, int distance) 47       { 48         this.Begin = begin; 49         this.End = end; 50         this.Distance = distance; 51       } 52  53       public int Begin { get; private set; } 54       public int End { get; private set; } 55       public int Distance { get; private set; } 56     } 57  58     class Graph 59     { 60       private Dictionary<int, List<Edge>> _adjacentEdges 61         = new Dictionary<int, List<Edge>>(); 62  63       public Graph(int vertexCount) 64       { 65         this.VertexCount = vertexCount; 66       } 67  68       public int VertexCount { get; private set; } 69  70       public void AddEdge(int begin, int end, int distance) 71       { 72         if (!_adjacentEdges.ContainsKey(begin)) 73         { 74           var edges = new List<Edge>(); 75           _adjacentEdges.Add(begin, edges); 76         } 77  78         _adjacentEdges[begin].Add(new Edge(begin, end, distance)); 79       } 80  81       public int[] Dijkstra(int source) 82       { 83         // dist[i] will hold the shortest distance from source to i 84         int[] distSet = new int[VertexCount]; 85  86         // sptSet[i] will true if vertex i is included in shortest 87         // path tree or shortest distance from source to i is finalized 88         bool[] sptSet = new bool[VertexCount]; 89  90         // initialize all distances as INFINITE and stpSet[] as false 91         for (int i = 0; i < VertexCount; i++) 92         { 93           distSet[i] = int.MaxValue; 94           sptSet[i] = false; 95         } 96  97         // distance of source vertex from itself is always 0 98         distSet[source] = 0; 99 100         // find shortest path for all vertices101         for (int i = 0; i < VertexCount - 1; i++)102         {103           // pick the minimum distance vertex from the set of vertices not104           // yet processed. u is always equal to source in first iteration.105           int u = CalculateMinDistance(distSet, sptSet);106 107           // mark the picked vertex as processed108           sptSet[u] = true;109 110           // update dist value of the adjacent vertices of the picked vertex.111           for (int v = 0; v < VertexCount; v++)112           {113             // update dist[v] only if is not in sptSet, there is an edge from 114             // u to v, and total weight of path from source to  v through u is 115             // smaller than current value of dist[v]116             if (!sptSet[v]117               && distSet[u] != int.MaxValue118               && _adjacentEdges[u].Exists(e => e.End == v))119             {120               int d = _adjacentEdges[u].Single(e => e.End == v).Distance;121               if (distSet[u] + d < distSet[v])122               {123                 distSet[v] = distSet[u] + d;124               }125             }126           }127         }128 129         return distSet;130       }131 132       /// <summary>133       /// A utility function to find the vertex with minimum distance value, 134       /// from the set of vertices not yet included in shortest path tree135       /// </summary>136       private int CalculateMinDistance(int[] distSet, bool[] sptSet)137       {138         int minDistance = int.MaxValue;139         int minDistanceIndex = -1;140 141         for (int v = 0; v < VertexCount; v++)142         {143           if (!sptSet[v] && distSet[v] <= minDistance)144           {145             minDistance = distSet[v];146             minDistanceIndex = v;147           }148         }149 150         return minDistanceIndex;151       }152     }153   }154 }