深入分析 （迪杰斯特拉算法） Dijkstra 算法实现原理

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
基本思想

     通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

     此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

     初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是"起点s到该顶点的路径"。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。

操作步骤

(1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

(4) 重复步骤(2)和(3)，直到遍历完所有顶点。

单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。

如下图有权图，Dijkstra算法可以计算任意节点到其他节点的最短路径

算法图解

1.选定A节点并初始化，如上述步骤3所示

2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合

3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ，如图所示这时候A->B距离 其实为 A->D->B

1. 思路就是这样，往后就是大同小异了

1. 算法结束

c# 代码实现

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 迪杰斯特拉算法
{
    struct Graph 
    {
        public char[] vexs;            // 顶点集合
        public int vexnum;             // 顶点数
        public int edgnum;             // 边数
        public int[,] matrix;          // 邻接矩阵
    };

    class Program
    { 
        static void Main(string[] args)
        {
            Graph g;
            g.vexs = new char[]{'A','B','C','D','E'};
            g.vexnum = 5;
            g.edgnum = 7;
            g.matrix = new int[5,5]{
                {0,4,int.MaxValue,2,int.MaxValue},
                {4,0,4,1,int.MaxValue},
                {int.MaxValue,4,0,1,3},
                {2,1,1,0,7},
                {int.MaxValue,int.MaxValue,3,7,0}
            };

            dijkstra(g,0);

            Console.ReadKey();

        }
        private static void dijkstra(Graph g,int vs)
        {
            int k = vs;
            int min = int.MaxValue;
            int tmp;
            int[] flag = new int[100];             // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
            int[] dist = new int[100];
            int[] prev = new int[100];

            for (int i = 0; i < g.vexnum; i++)
            {
                flag[i] = 0;                          // 顶点i的最短路径还没获取到。
                prev[i] = 0;                          // 顶点i的前驱顶点为0。
                dist[i] = g.matrix[vs, i];            // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
            }

            // 对 vs 进行初始化
            flag[vs] = 1;
            dist[vs] = 0;

            for (int i = 1; i < g.vexnum; i++)
            {
                min = int.MaxValue;
                for (int j = 0; j < g.vexnum; j++)
                {
                    if (flag[j] == 0 && dist[j] < min)
                    {
                        min = dist[j];
                        k = j;
                    }
                }

                flag[k] = 1;

                for (int n = 0; n < g.vexnum; n++)
                {
                    tmp = g.matrix[k, n] == int.MaxValue ? int.MaxValue : (min + g.matrix[k, n]);
                    if (flag[n] == 0 && tmp < dist[n])
                    {
                        dist[n] = tmp;
                        prev[n] = k;
                    }
                }

            }

            for (int i = 0; i < g.vexnum; i++)
            {
                Console.WriteLine("点：" + g.vexs[vs] + " 到点：" + g.vexs[i] + "的最短距离为：" + dist[i]);
            }

        }
    }


}

运行结果