Dijkstra算法C#演示程序

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

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();
        }
    }
}