Dijkstra 单源最短路径算法

 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 source
10         end if 
11         add v to Q               // All nodes initially in Q (unvisited nodes)
12     end for
13     
14     while Q is not empty:
15         u ← vertex in Q with min dist[u]  // Source node in first case
16         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 found
21                 dist[v] ← alt 
22                 prev[v] ← u 
23             end if
24         end for
25     end while
26 
27     return dist[], prev[]
28 
29 end function

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                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 vertices
101         for (int i = 0; i < VertexCount - 1; i++)
102         {
103           // pick the minimum distance vertex from the set of vertices not
104           // yet processed. u is always equal to source in first iteration.
105           int u = CalculateMinDistance(distSet, sptSet);
106 
107           // mark the picked vertex as processed
108           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.MaxValue
118               && _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 tree
135       /// </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 }