DSP

最短路径-Dijkstra 算法

2019-07-13 12:56发布

本文首发于:算法社区 dspstack.com,转发请注明出处。

前言#

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止

使用场景#

  • 有向图
  • 没有负权边(邻接点之间的权重)

具体算法#

变量说明#

v_0:起始点;
w:邻接点之间的权重;
S:集合,所属其结点是已找到v0到该点的最短路径,称永久标号结点;
T :集合,所属其结点是还未找到最短路径的结点,称临时标号结点;
L_i:表示从起点 v_0 到 v_i 的最短路径上的权(此时,称为永久标号),或表示从起点 v_0 到 v_i 的最短路上的权的上界(此时,称为临时标号);
lamda_i:结点 vi 对应路径权值 L_i 的上一结点下标,用于反推最短路径;
(lamda_i,L_i):结点标号, lamda_i 和 L_i 的意义如上;
i:是下标。

算法描述#

为了说明方便,路径起结点下标为0,该结点邻接点分别1,2,3等,邻接点的邻接点的下标依次加1。
应用时,下标就是指向该结点的指针
file
Step1:令 u_i = 0, i = 0,lamda_i = -1 , u_j = +无穷, lamda_j = 0 (1 <= j <= n - 1),S = {v_0} ,T = {v_1,...,v_n-1},其中 S 中的点给予永久标号; T 中的点给予临时标号。
Step2:i = 0
Step3:如果 v_i 有邻接点,取 v_i 的邻接点 v_j, v_j 不属于 S,u_j = min{u_j,u_i + w(v_i,v_j)} ,如果 u_j < u_i + w(v_i,v_j),lamda_j = i ,否则 lamda_j 不变;否则转Step4。
Step4:u_k = min{u_j} ,v_j 属于 T,j = i + 1,...,n - 1, 如果 u_k = +无穷,则结束,起点到各点没有最短路径;否则转Step5;
Step5:S = S 并 {v_k},i = k , T 中删除 v_k;若 T 中已无元素,则结束,此时已求出起点到任意结点的最短路径;如果 v_k 是路径终点,则找到,结束;否则转step3。

算法结果#

v_i 的最短路径: lamda_i, lamda_i-1,…, lamda_0 。 本文首发于:算法社区 dspstack.com,转发请注明出处。