单源最短路

正权边

Dijkstra算法 O(n^2)

每次通过已知最短距离来更新到其他点的最短路
注意出现重边要进行比较

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int g[N][N];//邻接矩阵
int dist[N];//源点到其他点的距离
bool st[N];//判断是否被认定为已经是最短
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	for(int i = 0; i < n - 1; i ++ )
	{
		int t = -1;// 在还未确定最短路的点中，寻找距离最小的点
		for(int j = 1; j <= n; j ++ )
			if(!st[j] && (t == -1 || dist[j] < dist[t]))
				t = j;
		// 用t更新其他点的距离
		for(int j = 1; j <= n; j ++ )
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		st[t] = true;
	}
	if(dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}

堆优化的Dijkstra算法 O(mlogn)

如果是稀疏图，点数量多，遍历的时候就会超时，所以用邻接表存储，每次取最短距离的步骤可以用最小堆优化

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n;
int h[N], w[N], ne[N], e[N], idx;
int dist[N];
int st[N];

int Dijkstra() {
	memset(h, -1, sizeof h);
	dist[1] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({0, 1});
	while (heap.size()) {
		PII t = heap.top();
		heap.pop();

		int ver = t.second, distance = t.first;
		if (st[ver])
			continue;
		st[ver] = true;

		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dist[j] > distance + w[i]) {
				dist[j] = distance + w[i];
				heap.push({dist[j], j});
			}
		}
	}
	if (dist[n] == 0x3f3f3f3f)
		return -1;
	return dist[n];
}

int main() {
	return 0;
}

负权边

Bellman-ford算法 O(nm)

Dijkstra算法无法处理有负权边的图
一层一层的去更新
有限步数的条件下只能用Bellman-ford算法

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)//从源点开始更新，每次更新一层(这是因为正无穷更新之后还是正无穷，所以可以一层一层更新)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

spfa算法 O(m)

队列优化的Bellman_ford算法
可以用来判断是否有负权回路,需要时只需要加一个cnt数组来记录点数，如果点数>n就说明存在负权环

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

多源汇最短路

Floyd算法

初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}