in Uncategorized |

Dijkstra算法C#演示程序

最近学习Dijkstra算法和C#，用C#写了一个Dijkstra算法的演示程序。图中的节点要求使用26个字母来表示。节点之间的距离为整数，不相邻节点输入”I”或”i”来代表Infinite。该程序移除了输入的冗余，并且显示输入节点和距离后的邻接矩阵。同时会在最终结果给出前，打印出 Dijkstra算法的计算过程表和最短路径点的次序（path数组）。在代码中给出了详细的注释，对于学习Dijkstra算法的人具有一定帮助。
运行效果图：
050615_0543_DijkstraC1.png

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace CsharpVersion
{
 
    class Program
    {
        public class DEF
        {
            public const int MAX = 26;
            public const int INF = 999999;
        }
        public struct Graph
        {
            public char[] vetx;//用于存储每个节点的名字
            public int vetxNum;//拥有节点的数量
            public int[,] matrix; //相邻矩阵
        }
 
        static public Graph genGraph()
        {
            string input;
            int i, j;
 
            //初始化图的结构体
            Graph map;
            map.vetx = new char[DEF.MAX];
            map.vetxNum = 0;
            map.matrix = new int[DEF.MAX, DEF.MAX];
 
            Console.Write("Please enter the number of nodes:");
            input = Console.ReadLine();
            map.vetxNum = Convert.ToInt32(input);
 
            //获取每一个节点的字母
            for (i = 0; i < map.vetxNum; i++)
            {
                Console.Write("Please enter the letter of nodes:");
                map.vetx[i] = Convert.ToChar(Console.ReadLine());
            }
            //创建邻接矩阵
            for (i = 0; i < map.vetxNum; i++)
                for (j = i + 1; j < map.vetxNum; j++) //只需输入半个矩阵
                {
                    Console.Write("Please enter the distance from {0} to {1} (I stands for Infinte):", map.vetx[i], map.vetx[j]);
                    input = Console.ReadLine();
                    if (input.ToLower() == "i")
                        map.matrix[i, j] = DEF.INF;
                    else
                        map.matrix[i, j] = Convert.ToInt32(input);
                }
            //填补节点自己到自己的距离 = 0
            for (i = 0; i < map.vetxNum; i++)
                map.matrix[i, i] = 0;
 
            //填补重复部分的矩阵
            for (i = map.vetxNum - 1; i > 0; i--)
                for (j = i - 1; j >= 0; j--)
                    map.matrix[i, j] = map.matrix[j, i];
 
            //debug: 显示邻接矩阵
            Console.WriteLine("*************START**************");
            Console.WriteLine("The matrix of distance is:");
            for (i = 0; i < map.vetxNum; i++)
            {
                for (j = 0; j < map.vetxNum; j++)
                {
                    Console.Write("{0}", map.matrix[i, j]);
                    Console.Write("\t");
                }
                Console.Write("\r\n");
            }
            Console.Write("\r\n");
            return map;
        }
 
        //Dijkstra algirthm
        static void dijkstra(Graph map, char sNode)
        {
            int[,] dist = new int[map.vetxNum, map.vetxNum];//距离数组
            bool[] flag = new bool[map.vetxNum]; //标记数组
            int min, tmp, preBaseVal = 0, i, j, preMarkedIndex, vs = 0;
            int[] path = new int[map.vetxNum]; //用于存储推演表中所有被选中的中继点
            Stack pathStack = new Stack();
 
            //找出起始点的编号
            for (i = 0; i < map.vetxNum; i++)
                if (map.vetx[i] == sNode)
                    vs = i;
            //距离数组初始化
            for (i = 0; i < map.vetxNum; i++)
            {
                dist[0, i] = DEF.INF; // map.matrix[vs, i];
                flag[i] = false;//所有节点标志位均设为未标记
            }
 
            //初始化起始点数据
            dist[0, vs] = 0;//起始点到自身的距离为0
            preMarkedIndex = vs;
 
            for (i = 0; i < map.vetxNum - 1; i++) //i代表第几行，
            {
                //在推演表中第一行找出最小数
                min = DEF.INF;
                for (j = 0; j < map.vetxNum; j++) //j代表第几列
                {
                    if (min > dist[i, j] && flag[j] == false)
                    {
                        min = dist[i, j];
                        preMarkedIndex = j;
                        preBaseVal = min; //记录本轮找到的最小值
                    }
                }
 
                flag[preMarkedIndex] = true;//将找到的节点标记
                path[i] = preMarkedIndex;//将找到的节点（次序）保存
 
                //把已标记的值复制到推演表下一行
                for (j = 0; j < map.vetxNum; j++)
                {
                    if (flag[j] == true) //找到已标记的节点
                        dist[i + 1, j] = dist[i, j]; //把上一行中对应的已标记值复制到本行中
                }
                //求出当前行未被标记列（节点）的距离
                for (j = 0; j < map.vetxNum; j++)
                {
                    if (flag[j] == false) //找出未标记节点
                    {
                        if (map.matrix[preMarkedIndex, j] == DEF.INF) //前驱结点到本列所指节点不可直接到达，复制上一行数据
                        {
                            dist[i + 1, j] = dist[i, j];
                            continue; //继续去判断下一个节点
                        }
                        else //前驱结到当前列所指节点可以直接到达时
                        {
                            dist[i + 1, j] = (dist[i, j] < (preBaseVal + map.matrix[preMarkedIndex, j]) ? dist[i, j] : (preBaseVal + map.matrix[preMarkedIndex, j]));
                        }
                    }
                }
            }
            for (j = 0; j < map.vetxNum; j++) //找出最后一个剩余的节点，并加入到路径数组中path[]
            {
                if (flag[j] == false) //最后剩余的节点尚未标记
                    path[map.vetxNum-1] = j;
            }
 
            //打印推演表
            Console.Write("\r\n");
            Console.WriteLine("The calculation table is:");
            for (i = 0; i < map.vetxNum; i++)
            {
                for (j = 0; j < map.vetxNum; j++)
                {
                    Console.Write("{0}", dist[i, j]);
                    Console.Write("\t");
                }
                Console.Write("\r\n");
            }
 
            //debug: path的内容
            Console.Write("Path=");
            for (i = 0; i < map.vetxNum; i++)
                Console.Write("{0}", map.vetx[path[i]]);
            Console.Write("\r\n\r\n");
 
            //找出路径结果
            for (i = 0; i < map.vetxNum; i++)
            {
                tmp = i; //tmp代表了第几列
                pathStack.Clear();//清空路径栈
                Console.Write("The shortest distance from {0} to {1} is {2}: ", map.vetx[vs], map.vetx[i], dist[map.vetxNum - 1, i]);
 
                //找出从给定点出发到达每一个节点的路径
                for (j = map.vetxNum - 1; j > 0; j--)
                {
                    if (j == map.vetxNum - 1) //j代表了第几行
                        pathStack.Push(map.vetx[i]); //将目的地节点压入路径栈
 
                    if (dist[j, tmp] == dist[j - 1, tmp])
                        continue;
                    else
                    {
                        pathStack.Push(map.vetx[path[j - 1]]);//将前驱结点名压入路径栈
                        tmp = path[j - 1]; //为下一次循环定位列，移动到前驱结点所在的列
                    }
                }
 
                //打印出路径栈中的路径
                foreach (char c in pathStack)
                {
                    Console.Write("->{0}", c);
                }
                Console.Write("\r\n");
            }
            Console.WriteLine("***************END***************");
        }
        static void Main(string[] args)
        {
            char startPoint;
            Graph map = genGraph();
 
            Console.Write("Please enter which node starts:");
            startPoint = Convert.ToChar(Console.Read());
 
            dijkstra(map, startPoint);
 
            Console.ReadKey();
        }
    }
}

Published

Updated