西安网站制作多少钱,电子商务网站建设预算,wordpress能做小程序,小笨鸟跨境电商平台前言
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的#xff0c;因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法#xff0c;解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展#xff0c;直到扩展到终点…前言
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展直到扩展到终点为止
使用场景
有向图没有负权边邻接点之间的权重
具体算法
变量说明
v_0起始点 w邻接点之间的权重 S集合所属其结点是已找到v0到该点的最短路径称永久标号结点 T 集合所属其结点是还未找到最短路径的结点称临时标号结点 L_i表示从起点 v_0 到 v_i 的最短路径上的权此时称为永久标号或表示从起点 v_0 到 v_i 的最短路上的权的上界此时称为临时标号 lamda_i结点 vi 对应路径权值 L_i 的上一结点下标用于反推最短路径 lamda_iL_i结点标号 lamda_i 和 L_i 的意义如上 i是下标。
算法描述
为了说明方便路径起结点下标为0该结点邻接点分别1,2,3等邻接点的邻接点的下标依次加1。 应用时下标就是指向该结点的指针 Step1令 u_i 0 i 0lamda_i -1 u_j 无穷 lamda_j 0 1 j n - 1S {v_0} T {v_1…v_n-1}其中 S 中的点给予永久标号 T 中的点给予临时标号。 Step2i 0 Step3如果 v_i 有邻接点取 v_i 的邻接点 v_j v_j 不属于 Su_j min{u_ju_i w(v_iv_j)} 如果 u_j u_i w(v_iv_j)lamda_j i 否则 lamda_j 不变否则转Step4。 Step4u_k min{u_j} v_j 属于 Tj i 1,…,n - 1 如果 u_k 无穷则结束起点到各点没有最短路径否则转Step5 Step5S S 并 {v_k}i k T 中删除 v_k若 T 中已无元素则结束此时已求出起点到任意结点的最短路径如果 v_k 是路径终点则找到结束否则转step3。
算法结果
v_i 的最短路径 lamda_i lamda_i-1…, lamda_0 。
