最短路Dijkstral算法

2020-07-05

最短路

给出有向图(或无向图)各边的长度

求任意两点间的最短路径长度

给出源点s，终点t可变

Floyd算法

问题一，有多个源点，采用Floyd算法
设定：有n个顶点，a[i][j]为顶点i到j的的距离，算法的核心操作为：

for (int i = 1; i <= n; i++)	a[i][i] = 0;

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][k] + a[k][j] < a[i][j]) {
                a[i][j] = a[i][k] + a[k][j];
                //如果是无向图，还要加一句
                //a[j][i] = a[i][k] + a[k][j];
            }
        }
    }
}

这个代码十分简单粗暴, 其中if那两句的操作叫松弛, 也是贯穿最短路算法的核心思想
如果a到b可以通过中转站来缩短距离，那就更新这个距离
Floyd算法就是通过对所有边都检查一遍来实现的，复杂度为O($n^3$)，好处就是任意两点的最短路都可以知道

Dijkstral算法

问题二，只有一个源点，采用Dijkstral算法
算法的思想是，每次从源点找一条最短的边，然后用这条边来更新源点到其他顶点的距离，然后将这条边拉黑
n个顶点的话最多只需要n-1次操作就可以了，n-1次选边，最多n-2次松弛，时间复杂度为O($n^2$)

int dist[maxn], a[maxn][maxn], vis[maxn], n, m, st, en;
//dist[i]是源点st到顶点i的最短距离, a[i][j]是顶点i到顶点j的初始距离(可能没有路)
//vis是在选边的时候用的，已经选过的边就不在使用，n为顶点数，m为边数，st源点，en终点

void Dijkstra(){
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
        dist[i] = a[st][i];
    }
    vis[st] = 1;
    dist[st] = 0;
    
    for(int i = 1; i <= n; i++){
        int k, mm = inf;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && mm > dist[j]){
                mm = dist[j];
                k = j;
            }
        } //以上为选边
        
        if(mm == inf)   break; //如果最短路不存在，说明已经过了n-1次了，直接退出
        vis[k] = 1; //把选中的边拉黑，下次就不选了
        
        for(int j = 1; j <= n; j++){
            if(!vis[j] && dist[j] > dist[k] + a[k][j]){
                dist[j] = dist[k] + a[k][j];
            }
        } //以上为松弛操作
    }
}

以上为Dijkstral的核心代码, 源点st到任意顶点的最短距离都可以知道