Monthly Archives: May 2015

Dijkstra算法详解

Dijkstra算法,中文翻译为迪杰斯特拉算法,是在带权有向图G = (V, W) (V是节点的集合,W是边上权值的集合,在集合W中,不直接相连的节点间的距离标记为无穷大)中求某个节点到其余节点之间最短路径的经典算法。该算法的核心思想是将图中所有的节点划分为2个集合,集合S包含已经找到最短路径的节点,集合U包含尚未找到最短路径的节点的距离(初始值全部设定为无穷大)。从某一点v开始采用广度优先遍历思想对图进行遍历,每找到一个节点的最短路径,就将该节点从集合U中移除,并加入到集合S中,直到最后U变为空集,S包含图中所有的节点到出发点的最小距离。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。

Dijkstra算法的过程:

  1. 选取某个节点v作为出发点,从出发点到出发点距离为0,即找到最小路径。将该出发点从集合U中移除并加入到集合S中。
  2. 在集合W中查看出发点v到集合U中各个节点的距离。找出距离最小的节点k(到k的最短路径找到),将k从集合U中移除并加入到集合S中。
  3. 以k作为中间点,在W中查看从k到U中节点m的距离,如果m在W中的值小于m在U中的值(k和m直接连接),将m在W中的值与k在U中的值相加(从v出发经过k到达m的距离),再将相加结果与W中v到m的值(v不经过中间点到m的距离)对比大小,选取较小的值跟新k在U中的数据。
  4. 在U中找出数值最小的节点n,该值即为v到n的最短路径。将n从集合U中移除并加入到集合S中。把n作为中间点重复第3、4步,直到U中所有的节点都移动到S中。

图1

Dijkstra算法的手算方法

如图1,从节点A开始。首先我们创建一个表,用该表记录每次运算的值。该表表头代表了集合U中包含的节点(未找出最短路径节点:A、B、C、D)。第2行将各节点的距离,初始化为无穷大,用INF表示。

 

A

B

C

D

 

INF

INF

INF

INF

 

点A是出发点,自身到自身的路径最短,为0,即A到A的最短路径找到。在A列的第2行输入0,并用下划线标出,表明将A从U中移除。在表的第2行最左侧写A,表示将A加入集合S。

 

B

C

D

0

INF

INF

INF

建立表格第3行。此时集合U中包含{B、C、D},由图可知A->B的距离为1(查询集合W),更新B列的数值,写入第3行。由图可知A->C的距离为5,更新B列的数值,写入第3行。由图可知A->D不可直达,标记为INF。在表第3行中对集合U中所拥有的元素{1,5,INF}求最小值,得到B,此时B列第3行数据即为A->B的最小路径。对B列第3行数据加下划线标识出,即将B移出集合U。同时在第3行最左端写B,即将B加入集合S中。

 

A

B

C

D

0

INF

INF

INF

0

1

5

INF

建立表格第4行。此时集合U中包含{C、D},节点B为中间点。由图可知B->C的距离为1,而A->B的距离保存在表B列中,是1,则A->B->C的距离为1+1=2。由表C列第3行数据可知目前到达C的距离为5(A直接到达C)。求两条路径的最小值min(5,1+1)=2;更新C列数据,将2写入C列第4行。由图可知B->D点的距离为1,则A->B->D的距离为1+1=2,而A->D不可直接抵达,故而取值无穷大INF(该值记录在集合W中,此时该值等于表中D列数据)。求两条路径的最小值min(INF,1+1)=2。更行D列数据,将2写入到D列第4行。对集合U中的数据取最小值,C和D均为2,任选一个,该节点到A的最短距离即被计算出来。比如选C。对C进行标记。

 

A

B

C

D

A

0

INF

INF

INF

B

0

1

5

INF

C

0

1

2

2

重复上面的操作,建立表格第5行。此时集合U中只包含{D},节点C为中间点。由图可知C->D的距离为1。而A->C的最短距离已经求出,在上表中C列第4行,为2(经过节点B)。故A->B->C->D的距离为2+1=3。表中D列第4行记录到达D点的最小路径为2(通过B点),求两条路径的最小值min(2,2+1)=2。即D点的最小路径为2,将2写入D列第5行并对D列第5行进行标记。此时集合U为空集,集合S中的元素为{A、B、C、D},计算完毕。表中第5行所记录数据即为A点到各点的最小路径值。

 

A

B

C

D

A

0

INF

INF

INF

B

0

1

5

INF

C

0

1

2

2

D

0

1

2

2

 

具体路径(经过的节点)可以通过回溯法求出。在最后一张表中找到要求点所在的列,从下向上回溯,当数值发生变化时,跳转到所在行所对应的S集合中的元素所在的列,记录下该点,然后继续回溯,直到到达出发点。

如求到达C点的具体路径,从C列第5行向上回溯,到达第3行时数值发生变化,第3行对应为S集合中的B,则从B列第3行向上回溯,到达B列第2行,数值发生变化,第2行所对应的集合S中的元素为A,是起点,回溯完成。具体路径即为A->B->C。

本思路所对应的C#源代码请参看《Dijkstra算法C#演示程序》一文。

Dijkstra算法C#演示程序

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

?View Code CSHARP
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<char> pathStack = new Stack<char>();
 
            //找出起始点的编号
            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();
        }
    }
}