最短路算法

单源最短路

固定出发点，求到达其它点的最短距离

(Dijkstra（迪杰斯特拉）算法

• 不能解决负权边

堆优化的Dijkstra

#define MAX_N 100000 //最大点的数量

struct Node { //堆优化 
    int e, dis;  // dis表示点s到点e的距离 
    bool operator< (const Node& a) const {
        return this->dis > a.dis;
    }
};

struct edge { // 某个一条边上的点与b点的距离为v
    int b, v;
};

int ans[MAX_N + 5]; //ans[i] 表示i到起点s的最短距离 
vector<vector<edge> > ed(MAX_N + 5, vector<edge>()); //建立邻接表 

int s, n, m; //分别表示起点，点的个数，边的数量；
priority_queue <Node> q;
 
void Dijkstra() {
    memset(ans, 0x3f, sizeof(ans)); //初始化极大值 
    q.push((Node){s, 0});
    ans[s] = 0;
    while (!q.empty()) { //队列中存的是局部最优或者全局最优的点、距离 
        Node tp = q.top();
        q.pop();
        if (tp.dis > ans[tp.e]) continue; // 当前保留的距离是最短的，不能用tp.dis去更新其他点的最短距离 
        //更新其它点的最短距离 
        for (int i = 0; i < (int)ed[tp.e].size(); i++) {
            if (ans[ed[tp.e][i].b] <= tp.dis + ed[tp.e][i].v) continue;
            ans[ed[tp.e][i].b] = tp.dis + ed[tp.e][i].v;
            q.push((Node){ed[tp.e][i].b, ans[ed[tp.e][i].b]});
        }
    }
}

线段树优化的Dijkstra

斐波拉契堆优化的Dijkstra

#### Bellman-ford

• 能解决负权边

小优化

struct edge {
    int s, e, v;
};

edge de[200005];
int n, m, s, ans[100005], edge_cnt;


#define min(a, b) ({\
    (a) > (b) ? (b) : (a);\
})

void Bellman_ford() { 
    memset(ans, 0x3f, sizeof(ans));
    ans[s] = 0;
    while (1) {
        int flag = 0; // 小优化
        for (int i = 0; i < edge_cnt; i++) {
            if (ans[de[i].e] > ans[de[i].s] + de[i].v) {
                ans[de[i].e] = ans[de[i].s] + de[i].v;
                flag = 1;
            }
            //ans[de[i].e] = min(ans[de[i].e], ans[de[i].s] + de[i].v);
        }
        if (flag == 0) break; //如果没有更新某两个点的最短距离，那么已经达到全局最优了 
    }
}

大优化

• 基于队列的Bellman-ford（SPFA）
• 由点s逐渐扩散，求得各个点到s的距离

bfs版的SPFA

#include <stdio.h>
 
struct edge {
    int e, v, next;
};


edge de[200005];
int n, m, s, ans[100005], edge_cnt;
int head[100005]; //链表头节点

#define min(a, b) ({\
    (a) > (b) ? (b) : (a);\
})
int q[100000]; //队列
int vis[100005];
void Bellman_ford() { 
    memset(ans, 0x3f, sizeof(ans));
    ans[s] = 0;
    q[0] = s;
    vis[s] = 1;
    int l = 0, r = 1;
    while (l < r) {
        int tp = q[l++];
        vis[tp] = 0;
        for (int i = head[tp]; i != -1; i = de[i].next) {
            if (ans[de[i].e] <= ans[tp] + de[i].v) continue;
            ans[de[i].e] = ans[tp] + de[i].v;
            if (vis[de[i].e]) continue;
            q[r++] = de[i].e;
            vis[de[i].e] = 1;
        }
    }
}

void add_edge(int a, int b, int c) {
    de[edge_cnt].e = b;
    de[edge_cnt].v = c;
    de[edge_cnt].next = head[a];
    head[a] = edge_cnt++;
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d %d %d", &n, &m, &s);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add_edge(a, b, c);
        add_edge(b, a, c);
    }
    Bellman_ford();
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i] == 0x3f3f3f3f ? -1 : ans[i]);
    }
    return 0;
}

dfs版的SPFA

多源最短路

求任意两点最短距离

Floyd

动态规划思想

#define min(a, b) ({\
    (a) > (b) ? (b) : (a);\
})
void Floyd() {
    //n表示点的个数， 点的编号从 1 开始 
    for (int k = 1; k <= n; k++) { // 中转站 
        for (int l = 1; l <= n; l++) {
            for (int r = 1; r <= n; r++) {
                dis[l][r] = min(dis[l][r], dis[l][k] + dis[k][r]);
            }
        }
    }
}

总结

算法名称	图存储方式	适合情况	时间复杂度	说明
Floyd	矩阵	多源	O(n^3)	可以存在负权边，图中不能存在环，能解决最长路径问题
Dijkstra	邻接表，链式前向星	单源	O(n ^ n)	不能存在负权边，不能存在负权环
优先队列优化的Dijksra	邻接表，链式前向星	单源	O(m * logn)，常数大	不能存在负权边，不能存在负权环
线段数优化的Dijksra	邻接表，链式前向星	单源	O(m * logn)，常数小	不能存在负权边，不能存在负权环
BEllman-ford	邻接表，链式前向星	单源	O(n * m)	能判断负环，不能解决负环最短路，边权可以为负，能解决最长路径问题
SPFA	邻接表，链式前向星	单源	O(n * m) 到 O(Km)	能判断负环，不能解决负环最短路，边权可以为负，能解决最长路径问题
斐波拉契堆优化的Dijkstra	邻接表，链式前向星	单源	O(m + nlogn)	不能存在负权边，不能存在负权环