单元汇最短路:
所有边都是正数:

dijkstraⅠ:

贪心思路 时间复杂度: O(n^2)

邻接矩阵存储图(技巧化处理重边情况)
初始化 dist, g 数组无穷大，最后无穷大的边便不是通路

迪杰斯特拉算法适用于求正权有向图中，源点到其余各个节点的最短路径。(图中可以有环，但不能有负权边)。

初始化点dist[0] = 1;

然后遍历，找出当前路径最短的一个点(dist)
将其赋值给 t;

然后依次遍历每个点，找出当前这个t点能够到达的点，将其赋值，(当前这个t点所能到达每个点的最小值)

循环，直到遍历完所有点，这时的图就是原点达到每个点的最小值

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f; // 用作无穷大的初始化值

int n, m;
int g[N][N]; // 邻接矩阵存储图
int dist[N]; // 存储从起点到每个节点的最短距离
bool st[N]; // 标记数组，记录节点的最短路径是否已经找到

// 实现 Dijkstra 算法
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); // 初始化所有距离为无穷大
    dist[1] = 0; // 起点到自己的距离为 0

    for (int i = 0; i < n; i++) 
    {
        int t = -1;
        // 寻找未确定最短路径的距离最小的节点
        for (int j = 1; j <= n; j++)
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j;
            }
        }
        // 使用找到的节点 t 更新其他节点的距离
        for (int j = 1; j <= n; j++)
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
        dist[j] 是当前已知的从起点到节点 j 的最短路径长度。
        dist[t] 是从起点到当前节点 t 的最短路径长度，这个长度在选择 t 之前已经确定。
        g[t][j] 是从节点 t 到节点 j 的直接距离（如果 t 和 j 之间没有直接的边，这个值会是一个非常大的数，通常是初始化时的值）。
        min(dist[j], dist[t] + g[t][j]) 比较当前已知的最短路径长度 dist[j] 和通过 t 到达 j 的路径长度 dist[t] + g[t][j]，取二者中的较小值作为新的最短路径长度。这就是所谓的“松弛”操作。

        st[t] = true; // 标记节点 t 的最短路径已经找到
    }

    if (dist[n] == INF) return -1; // 如果终点的最短路径长度仍为无穷大，说明无法到达终点
    return dist[n]; // 返回终点的最短路径长度
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g); // 初始化图的邻接矩阵为无穷大

    // 读入边信息并构建图
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c); // 处理重边情况
    }

    printf("%d\n", dijkstra()); // 计算并打印最短路径长度

    return 0;
}

dijkstra Ⅱ:
(堆优化版)

时间复杂度:O(mlogn)

邻接表存储图(用一个小根堆，加pair存储{dist,当前节点))

再就是一些初始化的问题(多练就好)

利用堆:
找出没有被遍历过且距离最近的点
(与朴素dijkstra算法一样)
遍历当前邻接表;
如果距离小于当前这个点的dist距离
则更新

循环，直到堆空(所有点均以更新最小距离)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> PII; // 使用pair来存储两个整数的组合，通常用于表示距离和节点编号

const int N = 1e6 + 10; // 定义最大的节点数量
const int INF = 0x3f3f3f3f; // 使用一个较大的数表示无穷大，用于初始化距离

int n, m; // n 表示节点的数量，m 表示边的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表表示图，e[]存储边的目标节点，w[]存储边的权重，ne[]存储下一条边的索引，h[]存储每个节点的边链表头，idx为边的索引
int dist[N]; // 存储从起点到每个节点的最短距离
bool st[N]; // 标记数组，用于标记节点的最短路径是否已经找到

// 向图中添加边
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// 实现Dijkstra算法
int dijkstra() 
{
    memset(dist, INF, sizeof dist); // 初始化所有节点到起点的距离为无穷大
    dist[1] = 0; // 起点到自己的最短距离为0
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个最小堆，用于按距离排序存储节点
    heap.push({0, 1}); // 将起点压入最小堆

    while (heap.size()) 
    {
        auto t = heap.top(); // 取出堆顶元素，即当前距离最小的节点
        heap.pop();

        int ver = t.second; // 当前节点编号
        if (st[ver]) continue; // 如果当前节点的最短路径已经找到，则跳过
        st[ver] = true; // 标记当前节点的最短路径已找到

        for (int i = h[ver]; i != -1; i = ne[i]) 
        { // 遍历当前节点的所有邻接节点
            int j = e[i]; // 邻接节点编号
            if (dist[j] > dist[ver] + w[i]) 
            { // 如果存在更短的路径，则更新
                dist[j] = dist[ver] + w[i]; // 更新最短距离
                heap.push({dist[j], j}); // 将更新后的节点压入最小堆
            }
        }
    }

    if (dist[n] == INF) return -1; // 如果终点的最短路径长度仍为无穷大，说明无法到达终点
    return dist[n]; // 返回终点的最短路径长度
}

int main() 
{
    cin >> n >> m; // 输入节点数和边数

    memset(h, -1, sizeof h); // 初始化邻接表，所有链表头指向-1，表示空链表
    while (m--)
    {
        int a, b, c; // 输入边的起点，终点和权重
        cin >> a >> b >> c;
        add(a, b, c); // 向图中添加边
    }

    cout << dijkstra() << endl; // 输出从起点到终点的最短路径长度

    return 0;
}

bellman_ford:(存在负权边， 对边数有限制)
时间复杂度为O(nm);

看收藏
backup数组
用上一轮的状态来更新，如果不用backup，本来是上一轮的a更新b，结果造成这一轮已经更新过的a更新b，造成错误

最后依次在k次数的限制下 对每一个节点不断更新

每次迭代k次，如果进行松弛操作，那他一定是经历了k条边的最短路，一共是n个节点，如果图里不存在负环，那么某点到零一点的最短路最多有n-1条边，有负环的图求最短路就没有意义
Bellman_ford算法可以存在负权回路，是因为其循环的次数是有限制的因此最终不会发生死循环；

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010; // N表示最大节点数，M表示最大边数

// 定义边的结构体，包含起点a，终点b，权重c
struct Edge 
{
    int a, b, c;
} edges[M];

int n, m, k; // n表示节点数，m表示边数，k表示迭代次数
int dist[N]; // dist数组存储从起点到每个节点的最短距离
int last[N]; // last数组用于在每次迭代中暂存上一轮的最短距离结果

// 实现Bellman-Ford算法
void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist); // 初始化所有节点到起点的距离为无穷大
    dist[1] = 0; // 起点到自己的最短距离为0

    // 进行k轮迭代，每轮尝试通过所有边进行松弛操作
    for (int i = 0; i < k; i++)
    {
        memcpy(last, dist, sizeof dist); // 暂存当前的最短距离结果

        // 遍历所有边，尝试进行松弛操作
        for (int j = 0; j < m; j++)
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c); // 使用暂存的结果进行松弛
        }
    }
}

int main() 
{
    scanf("%d%d%d", &n, &m, &k); // 读入节点数，边数和迭代次数

    // 读入所有边的信息
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }

    bellman_ford(); // 调用Bellman-Ford算法计算最短路径

    // 如果从起点到终点的最短距离大于一个很大的值的一半，认为终点不可达
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]); // 否则输出最短距离

    return 0;
}

spfa:
算法是由Bellman_ford算法优化而来，在最坏的情况下时间复杂度和它一样即时间复杂度为 O(nm)，一般情况下为O(m);

比较万能;

队列优化的bellman-ford算法
SPFA算法,相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的n和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。

对于bellman-ford算法来讲，减少了更新节点的次数，主要是因为，spfa对于已经在队列中的点，不会去将其添加入队列之中，只需要更新他的值即可(在树的遍历中完成这个操作)。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int N = 1e6 + 10; // 定义最大的节点数量
const int INF = 0x3f3f3f3f; // 定义一个大整数，用于初始化所有距离为无穷大

int n, m; // n 为图中的节点数，m 为边的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储图，e[] 存储边的目标节点，w[] 存储边的权重，ne[] 为下一条边的索引，h[] 存储每个节点的边的头部，idx 为当前边的索引
int dist[N]; // 存储从起点到每个节点的最短距离
bool st[N]; // 标记数组，用于记录节点是否已在队列中

// 向图中添加一条从 a 到 b 权重为 c 的有向边
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// 实现 SPFA 算法
int spfa() {
    memset(dist, INF, sizeof dist); // 初始化所有距离为无穷大
    dist[1] = 0; // 设置起点到自身的距离为 0
    queue<int> q; // 使用队列来进行节点的松弛操作
    q.push(1); // 起点入队
    st[1] = true; // 标记起点已经入队

    while (!q.empty()) { // 当队列不为空时进行循环
        int t = q.front(); // 取出队列头部的节点
        q.pop(); // 弹出队列头部的节点
        st[t] = false; // 标记该节点已经出队

        for (int i = h[t]; i != -1; i = ne[i]) { // 遍历所有从节点 t 出发的边
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) { // 如果可以通过 t 到达 j 使得距离更短
                dist[j] = dist[t] + w[i]; // 更新到达节点 j 的最短距离
                if (!st[j]) { // 如果节点 j 不在队列中
                    q.push(j); // 将节点 j 入队
                    st[j] = true; // 标记节点 j 已经入队
                }
            }
        }
    }

    if (dist[n] == INF) return -1; // 如果终点不可达，返回 -1
    return dist[n]; // 返回起点到终点的最短距离
}

int main() {
    cin >> n >> m; // 输入节点数和边数

    memset(h, -1, sizeof h); // 初始化邻接表
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c; // 输入每条边的起点，终点和权重
        add(a, b, c); // 向图中添加边
    }

    int result = spfa(); // 调用 spfa 算法计算最短路径
    if (result == -1) cout << "impossible" << endl; // 如果终点不可达，输出 impossible
    else cout << result << endl; // 否则，输出最短距离

    return 0;
}

spfa判断负环:

因为spfa算法对于到达不了的点，根本不会遍历，如果直接去判断有没有负环肯定是错的(这也是他能够适用于有负环的图的原因)，所以一开始要直接将所有点存入队列中，保证每个点都能被遍历到。
并且对每个点有用一个cnt数组存储他被松弛的次数，被松弛的次数大于了n说明一定有负环。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int N = 1e6 + 10; // 定义最大的节点数量
const int INF = 0x3f3f3f3f; // 使用一个较大的数表示无穷大，用于初始化距离

int n, m; // n 表示节点的数量，m 表示边的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表表示图，e[]存储边的目标节点，w[]存储边的权重，ne[]存储下一条边的索引，h[]存储每个节点的边链表头，idx为边的索引
int dist[N]; // 存储从起点到每个节点的最短距离
bool st[N]; // 标记数组，用于标记节点的最短路径是否已经找到
int cnt[N]; // 存储每个节点在SPFA过程中被松弛的次数

// 向图中添加一条从a到b，权重为c的有向边
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// 使用SPFA算法检测图中是否存在负权回路
bool spfa() 
{    // 这里不需要初始化dist数组为 正无穷/初始化的原因是， 如果存在负环， 那么dist不管初始化为多少， 都会被更新
    queue<int> q;
    for (int i = 1; i <= n; i++)
    //不仅仅是1了， 因为点1可能到不了有负环的点， 因此把所有点都加入队列
    { // 初始化，将所有节点入队，因为要检测负权回路
        st[i] = true;
        q.push(i);
    }

    while (q.size()) 
    { // 队列不为空时继续执行
        int 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])
            { // 如果可以通过t到j的路径更短
                dist[j] = dist[t] + w[i]; // 更新到达j的最短路径
                cnt[j] = cnt[t] + 1; // 更新j的被松弛次数
                if (cnt[j] >= n) return true; // 如果任何节点被松弛了n次或以上，则存在负权回路
                if (!st[j])
                { // 如果j不在队列中
                    q.push(j); // 将j加入队列
                    st[j] = true; // 标记j为在队列中
                }
            }
        }
    }
    return false; // 图中不存在负权回路
}

int main() 
{
    cin >> n >> m; // 输入节点数和边数

    memset(h, -1, sizeof h); // 初始化邻接表，所有链表头指向-1，表示空链表
    while (m--) 
    {
        int a, b, c; // 输入边的起点，终点和权重
        cin >> a >> b >> c;
        add(a, b, c); // 向图中添加边
    }

    // 使用SPFA算法检测图中是否存在负权回路
    if (spfa()) puts("Yes"); // 如果存在负权回路，输出"Yes"
    else puts("No"); // 否则，输出"No"

    return 0;
}

floyd算法:
三重循环
适用于求两个点之间的最短距离
多源汇最短路;
一些初始化的数据
没啥说的，
第一个循环是中间点，依次遍历，找出最短距离。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int N = 210, INF = 1e9; // 定义最大节点数和表示无穷大的值

int d[N][N]; // 存储所有节点对之间的最短路径长度
int n, m, Q; // n为节点数，m为边数，Q为查询次数

// Floyd-Warshall算法实现，计算所有节点对的最短路径
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]); // 通过中间节点更新最短路径
            }
        }
    }
}

int main()
{
    cin >> n >> m >> Q; // 读入节点数、边数和查询数

    // 初始化距离矩阵，自身到自身距离为0，其他为无穷大
    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;
        }
    }

    // 读入所有边的信息并更新距离矩阵
    while (m--) 
    {
        int a, b, w;
        cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w); // 对于重边，只保留最短的一条
    }

    floyd(); // 执行Floyd-Warshall算法计算所有节点对的最短路径

    // 处理查询，输出查询的两个节点之间的最短路径长度
    while (Q--) 
    {
        int a, b;
        cin >> a >> b;
        if (d[a][b] > INF / 2) cout << "impossible" << endl; // 如果两节点间不存在路径，输出impossible
        else cout << d[a][b] << endl; // 否则输出最短路径长度
    }

    return 0;
}