最短路径:Dijkstra算法 C#

  1     class Program
  2     {
  3         const int u = 10000;
  4 
  5         static void Main(string[] args)
  6         {
  7             Console.WriteLine("各点距离矩阵如下:");
  8             Console.WriteLine("   A  B  C  D  E");
  9             Console.WriteLine("A  0  2  3  /  /");
 10             Console.WriteLine("B  2  0  3  5  2");
 11             Console.WriteLine("C  3  3  0  2  4");
 12             Console.WriteLine("D  /  5  2  0  1");
 13             Console.WriteLine("E  /  2  4  1  0");
 14             int[,] matrix = new int[5, 5] { { 0, 2, 3, u, u }, { 2, 0, 3, 5, 2 }, { 3, 3, 0, 2, 4 }, { u, 5, 2, 0, 1 }, { u, 2, 4, 1, 0 } };
 15             while (true)
 16             {
 17                 Console.WriteLine("请输入要计算的起始点：");
 18                 string a = Console.ReadLine();
 19                 int start;
 20                 switch (a.ToLower())
 21                 {
 22                     default:
 23                     case "a":
 24                         start = 0;
 25                         break;
 26                     case "b":
 27                         start = 1;
 28                         break;
 29                     case "c":
 30                         start = 2;
 31                         break;
 32                     case "d":
 33                         start = 3;
 34                         break;
 35                     case "e":
 36                         start = 4;
 37                         break;
 38                 }
 39                 var list = Dijkstra(matrix, start);
 40 
 41                 for (int i = 0; i < list.Count; i++)
 42                 {
 43                     Console.WriteLine("从" + a.ToUpper() + "出发到" + i.IndexToChar() + "的最短距离为:" + list[i].Distance + ",最短路径为:" + list[i].Path);
 44                 }
 45             }
 46         }
 47 
 48         public static List<ShortPath> Dijkstra(int[,] matrix, int start)
 49         {
 50             int n = matrix.GetLength(0);
 51             int[] visited = new int[n];
 52             var list = new List<ShortPath>();
 53 
 54             for (int i = 0; i < n; i++)
 55             {
 56                 list.Add(new ShortPath() { Index = i, Name = start.IndexToChar() + "->" + i.IndexToChar(), Path = start.IndexToChar() + "->" + i.IndexToChar(), Distance = 0 });
 57             }
 58             visited[start] = 1;
 59             for (int i = 1; i < n; i++)
 60             {
 61                 int k = -1;
 62                 int dmin = u;
 63                 for (int j = 0; j < n; j++)
 64                 {
 65                     if (visited[j] == 0 && matrix[start, j] < dmin)
 66                     {
 67                         dmin = matrix[start, j];
 68                         k = j;
 69                     }
 70                 }
 71 
 72                 list[k].Distance = dmin;
 73 
 74                 visited[k] = 1;
 75                 for (int j = 0; j < n; j++)
 76                 {
 77                     if (visited[j] == 0 && matrix[start, k] + matrix[k, j] < matrix[start, j])
 78                     {
 79                         matrix[start, j] = matrix[start, k] + matrix[k, j];
 80                         list[j].Path = list[k].Path + "->" + j.IndexToChar();
 81                     }
 82                 }
 83             }
 84 
 85             return list;
 86         }
 87     }
 88 
 89     public static class Common
 90     {
 91         /// <summary>
 92         /// 索引转换字母
 93         /// </summary>
 94         /// <param name="index">当前索引</param>
 95         /// <param name="startIndex">起始索引 默认0</param>
 96         /// <returns></returns>
 97         public static char IndexToChar(this int index, int startIndex = 0)
 98         {
 99             return (char)('A' + index - startIndex);
100         }
101     }
102 
103     public class ShortPath
104     {
105         private int index;
106         private string name;
107         private string path;
108         private int distance;
109 
110         public string Path { get => path; set => path = value; }
111         public int Distance { get => distance; set => distance = value; }
112         public string Name { get => name; set => name = value; }
113         public int Index { get => index; set => index = value; }
114     }