Dijkstra 迪杰斯特拉算法 - lymanzhang/Machine-Learning-for-Design GitHub Wiki

算法简介

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

原理

  • 首先，引入一个辅助向量D，它的每个分量 D 表示当前所找到的 Dijkstra算法运行动画过程 Dijkstra算法运行动画过程 从起始点 （即源点 ）到其它每个顶点 的长度。 例如，D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。[1]
  • D的初始状态为：若从 到 有弧（即从 到 存在连接边），则D 为弧上的权值（即为从 到 的边的权值）；否则置D 为∞。 显然，长度为 D = Min{ D | ∈V } 的路径就是从 出发到顶点 的长度最短的一条路径，此路径为( )。
  • 那么，下一条长度次短的是哪一条呢？也就是找到从源点 到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点 到顶点 的最短路径长度。 假设该次短路径的终点是 ，则可想而知，这条路径要么是( )，或者是( )。它的长度或者是从 到 的弧上的权值，或者是D 加上从 到 的弧上的权值。
  • 一般情况下，假设S为已求得的从源点 出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为 ）要么是弧( )，或者是从源点 出发的中间只经过S中的顶点而最后到达顶点 的路径。 因此，下一条长度次短的的最短路径长度必是D = Min{ D | ∈V-S }，其中D 要么是弧( )上的权值，或者是D ( ∈S)和弧( , )上的权值之和。

算法描述如下：

  • 令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从 出发的的终点的集合，初始状态为空集。那么，从 出发到图上其余各顶点 可能达到的长度的初值为D=arcs[Locate Vex(G, )]， ∈V；
  • 选择 ，使得D =Min{ D | ∈V-S } ；
  • 修改从 出发的到集合V-S中任一顶点 的最短路径长度。

问题描述

在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短值。

算法思想

按路径长度递增次序产生算法： 把顶点集合V分成两组： （1）S：已求出的顶点的集合（初始时只含有源点V0） （2）V-S=T：尚未确定的顶点集合 将T中顶点按递增的次序加入到S中，保证： （1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 （反证法可证）

求最短路径步骤

算法步骤如下： G={V,E}

  • 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值 若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 若不存在<V0,Vi>，d(V0,Vi)为∞
  • 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
  • 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
  • 重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

算法代码

//初始化路径，都为最大值。
intpath[][]=newint[n+1][n+1];

for (inti=1; i<n+1; i++) {
    for (intj=1; j<n+1; j++)
        path[i][j]=Integer.MAX_VALUE;
}

//这里需要输入path[i][j]的具体内容，如果有重复数据的话，需要更新路径为最小值。
intminLen[]=newint[n+1];
//visit初始为0，防止回溯
intvisit[]=newint[n+1];
//初始化1到其他点的距离。

for (inti=1; i<n+1; i++) {
    minLen[i]=path[1][i];
}

voidDijkstra() {
    minLen[1]=0;
    visit[1]=1;
    intminj=1;
    for (inti=1; i<n+1; i++) {
        intmin=Integer.MAX_VALUE;
        for (intj=1; j<n+1; j++) {
            if (visit[j]==0&&minLen[j]<min) {
                min=minLen[j];
                minj=j;
            }
        }
        visit[minj]=1;
        for (intj=1; j<n+1; j++) {
            if (visit[j]==0&&minLen[minj]!=Integer.MAX_VALUE&&path[minj][j]!=
                Integer.MAX_VALUE&&minLen[j]>(minLen[minj]+path[minj][j])) {
                minLen[j]=minLen[minj]+path[minj][j];
            }
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️