Dijkstra算法和最小生成树prim算法

一、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. 总边权最小
5. 生成树是什么

如果有 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 更新邻居
5. 但是含义不同

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 是“把所有点接进来总代价最小”。