一、Dijkstra 单源最短路
1. 前提条件

Dijkstra 用来求：从一个起点 start 到所有点的最短距离

要求：边权不能为负数

适合：

带权图
无负权边
单源最短路

2. 核心概念

维护两个数组：dist[i]

表示：从 start 到 i 的当前最短距离

visited[i]

表示：i 这个点的最短路是否已经确定

每一轮做两件事：

1. 从所有未确定的点里，找 dist 最小的点 u
2. 用 u 去更新它的邻接点 v

更新公式：

if(dist[v] > dist[u] + w)
{
    dist[v] = dist[u] + w;
}

这一步叫：松弛 relax

3. 图结构：邻接表
#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000
#define INF 1000000000

struct EdgeNode {
    int to;
    int weight;
    struct EdgeNode* next;
};

struct EdgeNode* adj[MAXN];

初始化：

void initGraph(int n)
{
    for(int i = 0; i < n; i++)
    {
        adj[i] = NULL;
    }
}

加有向边：

void addDirectedEdge(int u, int v, int w)
{
    struct EdgeNode* node =
        malloc(sizeof(struct EdgeNode));

    node->to = v;
    node->weight = w;
    node->next = adj[u];
    adj[u] = node;
}

加无向边：

void addUndirectedEdge(int u, int v, int w)
{
    addDirectedEdge(u, v, w);
    addDirectedEdge(v, u, w);
}

4. Dijkstra 
void dijkstra(int n, int start, int dist[])
{
    int visited[MAXN];

    for(int i = 0; i < n; i++)
    {
        dist[i] = INF;
        visited[i] = 0;
    }

    dist[start] = 0;
//这里先全部初始化，把最短路径先都设置为无穷，然后全部未遍历都是0，起始位置设置为0，起始到自己距离为0
    for(int step = 0; step < n; step++)
    {
        int u = -1;

        for(int i = 0; i < n; i++)
        {
            if(!visited[i] &&
               (u == -1 || dist[i] < dist[u]))
            {
                u = i;
            }
        }
//这里第一次就是找到start对应的位置之后停止，之后的循环需要找每次相邻的dist最小的值开始确定最小的i给到u，
//step 控制轮数
//u 每一轮清空给-1
//内层 for 每一轮重新找当前 dist 最小且没 visited 的点。也就是遇到visited遍历过的跳过到后面，找未遍历的
        if(u == -1 || dist[u] == INF)
        {
            break;
        }
//这里是如果找不到相邻的了，或者直接断开了，就停止循环了
        visited[u] = 1;

        struct EdgeNode* cur = adj[u];

        while(cur != NULL)
        {
            int v = cur->to;
            int w = cur->weight;

            if(!visited[v] &&
               dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
            }
//这里就是找到相邻的最短的路径更新到dist里面
            cur = cur->next;
        }
    }
}

5. 代码怎么理解

这段：

int u = -1;

for(int i = 0; i < n; i++)
{
    if(!visited[i] &&
       (u == -1 || dist[i] < dist[u]))
    {
        u = i;
    }
}

意思是：

从所有还没确定最短路的点中，
找 dist 最小的点。

这段：

if(u == -1 || dist[u] == INF)
{
    break;
}

意思是：

剩下的点已经到不了了，
直接结束。

这段：

if(dist[v] > dist[u] + w)
{
    dist[v] = dist[u] + w;
}

意思是：

如果 start -> u -> v
比原来的 start -> v 更短，
就更新 dist[v]。

6. 例子

图：

0 --2-- 1
|       |
5       1
|       |
2-------

边：

0-1 权值2
0-2 权值5
1-2 权值1

从 0 开始。

初始：

dist[0]=0
dist[1]=INF
dist[2]=INF

选 0：

更新 1：dist[1]=2
更新 2：dist[2]=5

现在：

dist = [0,2,5]

选 1：

通过 1 到 2：
dist[2] = min(5, 2+1) = 3

现在：dist = [0,2,3]

选 2，结束。

答案：

0 到 0 = 0
0 到 1 = 2
0 到 2 = 3

7. Dijkstra 总结
Dijkstra

解决：
    单源最短路

条件：
    边权 >= 0

核心：
    每次选 dist 最小且未确定的点

更新：
    dist[v] = min(dist[v], dist[u] + w)

二、最小生成树 MST

1. 前提条件

最小生成树只针对：无向连通带权图

目标：

选出一些边，把所有点连起来，并且总权值最小

要求：

1. 所有点连通
2. 没有环
3. 边数是 n-1
4. 总边权最小
2. 生成树是什么

如果有 n 个点，那么生成树一定有：

n - 1 条边

例如 4 个点，生成树有 3 条边。

少于 n-1 条边，可能连不起来
多于 n-1 条边，一定有环

3. 最小生成树和最短路区别

最短路：关心从一个点到另一个点的路径最短

最小生成树：关心把所有点连起来总代价最小

它们不是一个问题。

三、Prim 算法

1. 前提条件

Prim 用来求：最小生成树

适合：无向连通带权图

2. 核心概念

Prim 的思想：

从一个点开始，逐渐扩大生成树。
每次选择一条最便宜的边，把一个新点加入生成树。

维护两个数组：lowCost[i]

表示：当前生成树连接到 i 点的最小边权

visited[i]

表示：i 是否已经加入生成树

3. 和 Dijkstra 最像的地方

Prim 每轮也是：

从未加入的点中，找 lowCost 最小的点 u。

然后加入生成树：

visited[u] = 1;

4. 和 Dijkstra 最大区别

Dijkstra 更新：

dist[v] = dist[u] + w;

意思：

从 start 到 v 的路径长度

Prim 更新：

lowCost[v] = w;

意思：

生成树连到 v 的最小边权

Prim 不关心路径总长度，只关心：
把一个新点接进树，用哪条边最便宜

5. Prim 代码
int prim(int n, int start)
{
    int lowCost[MAXN];
    int visited[MAXN];

    for(int i = 0; i < n; i++)
    {
        lowCost[i] = INF;
        visited[i] = 0;
    }

    lowCost[start] = 0;
//还是初始化之后把start对应的花费设为0
    int total = 0;

    for(int step = 0; step < n; step++)
    {
        int u = -1;

        for(int i = 0; i < n; i++)
        {
            if(!visited[i] &&
               (u == -1 || lowCost[i] < lowCost[u]))
            {
                u = i;
            }
        }
//这里还是每一轮找花费最小的元素
        if(u == -1 || lowCost[u] == INF)
        {
            return -1;
        }

        visited[u] = 1;
//被认定遍历过之后就加入生成树
        total += lowCost[u];

        struct EdgeNode* cur = adj[u];

        while(cur != NULL)
        {
            int v = cur->to;
            int w = cur->weight;
//这里不是对应要求最短路径，只更新对应每个节点的最小花费
            if(!visited[v] &&
               w < lowCost[v])
            {
                lowCost[v] = w;
            }

            cur = cur->next;
        }
    }

    return total;
}

6. 代码怎么理解

初始化：

lowCost[start] = 0;

意思：

从 start 开始建树，
把 start 加入树不需要花钱。

每轮：

int u = -1;

for(int i = 0; i < n; i++)
{
    if(!visited[i] &&
       (u == -1 || lowCost[i] < lowCost[u]))
    {
        u = i;
    }
}

意思：找当前最便宜能接入生成树的点。

加入总代价：

total += lowCost[u];

意思：

把 u 接入生成树需要花 lowCost[u]。

更新邻居：

if(!visited[v] && w < lowCost[v])
{
    lowCost[v] = w;
}

意思：

如果从 u 接到 v 更便宜，
就更新 v 的接入成本。

7. Prim 例子

图：

0 --2-- 1
|       |
5       1
|       |
2-------

边：

0-1 = 2
0-2 = 5
1-2 = 1

从 0 开始。

初始：

lowCost[0]=0
lowCost[1]=INF
lowCost[2]=INF

加入 0：

更新：
lowCost[1]=2
lowCost[2]=5

选最小：

1，花费2

加入 1：

通过边 1-2，权值1
lowCost[2]=min(5,1)=1

选：

2，花费1

总代价：0 + 2 + 1 = 3

最小生成树边权和：3

四、Dijkstra 和 Prim 对比

1. 代码结构像

它们都：

1. 初始化数组
2. 每轮找一个当前最小的点
3. visited[u] = 1
4. 用 u 更新邻居
2. 但是含义不同

Dijkstra：

dist[i] 表示 start 到 i 的最短路径长度

Prim：

lowCost[i] 表示当前生成树接到 i 的最小边权
3. 更新公式不同

Dijkstra：

dist[v] = dist[u] + w;

Prim：

lowCost[v] = w;

五、完整使用例子
int main()
{
    int n = 3;

    initGraph(n);

    addUndirectedEdge(0, 1, 2);
    addUndirectedEdge(0, 2, 5);
    addUndirectedEdge(1, 2, 1);

    int dist[MAXN];

    dijkstra(n, 0, dist);

    printf("Dijkstra:\n");

    for(int i = 0; i < n; i++)
    {
        printf("0 -> %d = %d\n", i, dist[i]);
    }

    int mst = prim(n, 0);

    printf("Prim MST = %d\n", mst);

    return 0;
}

输出应该是：

Dijkstra:
0 -> 0 = 0
0 -> 1 = 2
0 -> 2 = 3

Prim MST = 3

六、总结
Dijkstra

问题：
    从一个起点到所有点的最短路

条件：
    边权非负

数组：
    dist[i] = start 到 i 的当前最短距离

每轮：
    找未确定点中 dist 最小的点 u

更新：
    dist[v] = min(dist[v], dist[u] + w)

--------------------------------

最小生成树 MST

问题：
    把所有点连起来，并且总代价最小

条件：
    无向连通带权图

特点：
    n 个点
    n-1 条边
    无环
    连通

--------------------------------

Prim

问题：
    求最小生成树

数组：
    lowCost[i] = 当前生成树接到 i 的最小边权

每轮：
    找未加入生成树中 lowCost 最小的点 u

更新：
    lowCost[v] = min(lowCost[v], w)

--------------------------------

最大区别：

Dijkstra 看路径总长度：

    dist[u] + w

Prim 看接入生成树的单条边：

    w

Dijkstra 是“从起点走到各点最短”；
Prim 是“把所有点接进来总代价最小”。