最短路DijkStra’s Algorithm算法详解

dijkstra（图解）

概念：

Weight[m,n]: 二维数组,代表节点m到节点n的权重,即图上每条边的权重值.

WeightMin[n]: 一维数组,代表从开始节点0到节点n的已知通路上,所有已计算的权重之和的最小值.用来存放每一次计算的最小值.

FinalSet:已经确认的最终节点的集合

图上数据说明: 节点从左上点到右下点，从左到右从上到下，坐标从0开始到8

Weight[m,n]数据如下

	n0	n1	n2	n3	n4	n5	n6	n7	n8
n0		2		9	6
n1			1
n2					4		6
n3								4
n4				2		9		7
n5							5		1
n6									5
n7						1			5
n8

算法基本原理

基础原理其实很直白朴素，就是从开始节点起，计算所有能到达终止节点的通路的距离。从这些通路中找寻权重和最小的那一条通路。

不过这种朴素的找法随着节点数增加由于组合爆炸的原因，计算复杂度是呈阶乘级上升的，比指数级还恐怖.

然后在这个原理的基础上做一下优化，因为对于到达之前某个节点的最短距离已经确定了之后，我们可以该节点的最短距离存起来，当计算它之后的节点通路时，就直接拿出来用，而不需要再重头计算之前的那些节点。

优化后的算法只做2件事

【P1】第一，不断运行【广度优先算法】，优先找到最接近源点的所有可见点(能与已知节点直接连通的点)，计算这些可见点到源点的距离长度，由于一个节点可能有多条通路，所以当计算该点到源点的另一条通路的距离长度时，要与之前的WeightMin[n]取最小值然后再更新。

【P2】第二，每当运行完单次【广度优先算法】后，使用【贪心算法】，从所有已知路径中选择长度最短的那条路径，将顶点归入最终节点集合里FinalSet里，然后再从该节点运行【广度优先算法】，直至图里所有点都进入FinalSet里。

【贪心算法】保证了进入FinalSet里的节点距离一定是能到达该点的所有路径中最短的，不可能有其他到达该点更短的距离。

【广度优先算法】保证了在每次选择路径时，都能找到最短的一条路径。

流程开始：

图1

将所有节点权重和WeightMin[]更新为无穷大,暂时以99代替（因为所有节点权重和都没有比99更大的，可以用来代替无穷大）。

【P1】初始条件，从自己到自己的权重为0，WeightMin[0]=0，其余都是99。

【P2】将节点0归入最终节点集合里FinalSet里，FinalSet[]={0}，此时FinalSet未包含全部节点，所以即将对节点0运行【广度优先算法】

图2

【P1】对节点0运行【广度优先算法】，计算其所有可见点（n1,n3,n4）这3点到源点的通路的距离长度（使用已知的WeightMin[0]加上其直接连接的各边的权重Weight[0,(n1,n3,n4)]），分别是[0+2,0+9,0+6]。然后与之前的WeightMin[[1,3,4]]:[99,99,99]进行比较，取最小值(2<99,9<99,6<99)然后再更新，所以最后这3点的WeightMin[[1,3,4]]=[2,9,6]。

【P2】从所有已知路径顶点n1(2),n3(9),n4(6)中找长度最短的那条的顶点n1（即节点1），将其纳入最终节点集合FinalSet={0,1}，此时FinalSet未包含全部节点，所以即将对节点1运行【广度优先算法】

图3

【P1】对节点1运行【广度优先算法】，计算其所有可见点（n2,n4）到源点的通路的距离长度WeightMin[1]+Weight[1,(n2,n4)]=[2+1,2+3]。然后与之前的WeightMin[[2,4]:[99,6]进行比较更新，WeightMin[[2,4]]=[3,5]。

【P2】从所有已知路径顶点n2(3),n3(9),n4(5)中找长度最短的那条的顶点n2，将其纳入最终节点集合FinalSet={0,1,2}，此时FinalSet未包含全部节点，所以即将对进来的节点2运行【广度优先算法】

图4

【P1】对节点2运行【广度优先算法】，计算其所有可见点（n4,n6）到源点的通路的距离长度WeightMin[2]+Weight[1,(n4,n6)]=[3+1,3+6]。然后与之前的WeightMin[[4,6]:[5,99]进行比较更新，WeightMin[[4,6]=[4,9]。

【P2】从所有已知路径顶点n3(9),n4(4),n6(9)中找长度最短的那条的顶点n4，将其纳入最终节点集合FinalSet={0,1,2,4}，此时FinalSet未包含全部节点，所以即将对进来的节点4运行【广度优先算法】

图5

【P1】对上次归入FinalSet的节点运行【广度优先算法】求所有可见点的距离长度

g(n4) => (n3,n5,n7)

w(n3,n5,n7)=WeightMin[4]+Weight[4,(n3,n5,n7)]=[4+2,4+9,4+7]=[6,13,11]

WeightMin[[3,5,7]] = min([6,13,11] ,WeightMin[[3,5,7]]) = min([6,13,11] ,[9,99,99])=[6,13,11]

【P2】从所有已知路径顶点(=上一次全部顶点 - 上一次选中顶点 + 本次可见点)中选出长度最短的那条的顶点，归入FinalSet

min{n3,n5,n6,n7} = min{WeightMin[[3,5,6,7]]}=min([6,13,9,11])=6

n3

FinalSet={0,1,2,3,4}

图6

【P1】对上次归入FinalSet的节点运行【广度优先算法】求所有可见点的距离长度

g(n3) => (n7)

w(n7) = WeightMin[3]+Weight[3,(n7)] = [6+4] = [10]

WeightMin[7] = min([10] ,WeightMin[7]) = min([10] ,[11]) = [10]

【P2】在所有已知路径中选出最短路径对应的节点，归入FinalSet

min{n5,n6,n7} = min{WeightMin[[5,6,7]]} = min([13,9,10]) = 9

n6

FinalSet={0,1,2,3,4,6}

图7

【P1】对上次归入FinalSet的节点运行【广度优先算法】求所有可见点的距离长度

g(n6) => (n8)

w(n8) = WeightMin[6]+Weight[6,(n8)] = [9+5] = [14]

WeightMin[8] = min([14] ,WeightMin[8]) = min([14] ,[99]) = [14]

【P2】在所有已知路径中选出最短路径对应的节点，归入FinalSet

min{n5,n7,n8} = min{WeightMin[[5,7,8]]} = min([13,10,14]) = 10

n7

FinalSet={0,1,2,3,4,6,7}

图8

【P1】对上次归入FinalSet的节点运行【广度优先算法】求所有可见点的距离长度

g(n7) => (n5,n8)

w(n5,n8) = WeightMin[7]+Weight[7,(n5,n8)] = [10+1,10+5] = [11,15]

WeightMin[[5,8]] = min([11,15] ,WeightMin[[5,8]]) = min([11,15] ,[13,14]) = [11,14]

【P2】在所有已知路径中选出最短路径对应的节点，归入FinalSet

min{n5,n8} = min{WeightMin[[5,8]]} = min([11,14]) = 11

n5

FinalSet={0,1,2,3,4,6,7,5}

图9

【P1】对上次归入FinalSet的节点运行【广度优先算法】求所有可见点的距离长度

g(n5) => (n8)

w(n8) = WeightMin[5]+Weight[5,(n8)] = [11+1] = [12]

WeightMin[8] = min([12] ,WeightMin[8]) = min([12] ,[14]) = [12]

【P2】在所有已知路径中选出最短路径对应的节点，归入FinalSet

min{n8} = min{WeightMin[8]} = min([12]) = 12

n8

FinalSet={0,1,2,3,4,6,7,5,8}

至此，所有节点都进入FinalSet里

算法终止