当前位置：首页 > news >正文

图论算法：最短路径算法详解【c语言版】(无权最短路径、Dijkstra算法）

news 2024/11/14 0:50:56

别忘了请点个赞+收藏+关注支持一下博主喵！！！

图论算法：最短路径算法详解

在图论中，最短路径问题是寻找图中两点之间具有最小总权重的路径。这个问题在许多实际应用中都有重要的作用，比如网络路由、城市交通规划等。本文将探讨几种不同的最短路径算法，包括无权最短路径、Dijkstra算法、带负边值的图以及无圈图（DAG）的最短路径算法。

输入是一个赋权图：与每条边 (vi, vj) 相联系的是穿越该边的开销（或称为值）ci,j 。一条路径v1v2……vN的值是，这叫作赋权路径长(weighted path length)。而无权路径长只是路径上的边数，即 N-1。

单源最短路径问题(Single-Source Shortest-Path Problem)：

给定一个赋权图 G=(V, E) 和一个特定顶点 s 作为输入，找出从 s 到 G 中每一个其他顶点的最短赋权路径。

例如，在下图一个有向图中，从 v1 到 v6 的最短赋权路径的值为6，路径为 v1 -> v4 -> v7 -> v6 ；在这两个顶点间的最短无权路径长为2。

1. 无权最短路径

图3 表示一个无权图G，使用某个顶点 s 作为输入参数，我们想要找出从 s 到所有其他顶点的最短路径。显然，这是赋权最短路径问题的特殊情形，因为可以为所有的边都赋以权1。

设我们选择 s 为 v3，此时可立即得到 s 到 v3 的最短路径长为0，将其标记，如图4 所示。

然后开始寻找所有从 s 出发距离为1 的顶点，这可以通过考查邻接到 s 的那些顶点找到，即 v1 和 v6 ，将它表示在图5 中；然后找出从 s 出发最短路径恰为2 的顶点，找出所有邻接到 v1 和 v6 的顶点，这次搜索告诉我们，到 v2 和 v4 的最短路径长为2。

这种搜索图的方法就是广度优先搜索(breadth-first search)。该方法按层处理顶点：距开始点最近的那些顶点首先被求值，而最远的那些顶点最后被求值，这很像树的层序遍历(level-order traversal)。

图8 显示出该算法要用到的表的初始配置，记录了该算法的进行过程。对于每个顶点，我们跟踪3 条信息。首先，把从 s 开始到顶点的距离放到 dv 栏中，开始时除 s 外所有的顶点都不可达。pv 栏中的项为簿记变量，它将使我们显示出实际的路径。known 栏中的项在顶点被处理后置为 true。当一个顶点被标记为 known 时，我们就有了不会再找到更便宜的路径的保证，因此对该顶点的处理实质上已经完成。

代码实现1：

如下我们使用广度优先搜索（BFS）来实现。

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define INF 1000000typedef struct {int vertex;int distance;
} Node;void BFS(int adjMatrix[][MAX], int start, int n) {int queue[MAX];int front = -1, rear = -1;int visited[MAX] = {0};Node nodes[MAX];// 初始化起始节点nodes[start].vertex = start;nodes[start].distance = 0;visited[start] = 1;queue[++rear] = start;while (front != rear) {int current = queue[++front];for (int i = 0; i < n; i++) {if (adjMatrix[current][i] == 1 && !visited[i]) {nodes[i].vertex = i;nodes[i].distance = nodes[current].distance + 1;visited[i] = 1;queue[++rear] = i;}}}// 输出所有节点的距离for (int i = 0; i < n; i++) {printf("Node %d is %d steps away\n", i, nodes[i].distance);}
}int main() {int n = 6; // 节点数量int adjMatrix[MAX][MAX] = {0}; // 邻接矩阵初始化// 假设有一个无向图adjMatrix[0][1] = adjMatrix[1][0] = 1;adjMatrix[0][2] = adjMatrix[2][0] = 1;adjMatrix[1][3] = adjMatrix[3][1] = 1;adjMatrix[2][3] = adjMatrix[3][2] = 1;adjMatrix[2][4] = adjMatrix[4][2] = 1;adjMatrix[3][5] = adjMatrix[5][3] = 1;BFS(adjMatrix, 0, n); // 从节点0开始BFSreturn 0;
}

由于双层嵌套的 for 循环，因此该算法的运行时间为 O(|V|2)。一个明显的低效之处在于，尽管所有的顶点早已成为 known 了，但外层循环还是要继续，直到 NUM_VERTICES -1 为止。我们可以用类似于对拓扑排序所做的那样来排除这种低效性。在任一时刻，只存在两种类型其 dv ≠ ∞ 的 unknown 顶点。一些顶点的 dv =currDist，而其余的则有 dv = currDist + 1。这种想法可以通过使用一个队列而被进一步精化。其中数据变化如下图所示。

代码实现2：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> #define NUM_VERTICES 100 // 定义图中的顶点数量typedef struct {int dist;       // 从源顶点的距离int known;      // 是否已经确定最短路径int path;       // 路径上的前驱顶点
} Vertex;typedef struct Edge {int dest;       // 目标顶点索引struct Edge *next; // 指向邻接表中下一个边的指针
} Edge;// 函数声明
void unweighted(Vertex *vertices, Edge *adjList[], int s);
void addEdge(Edge *adjList[], int src, int dest);int main() {Vertex vertices[NUM_VERTICES];Edge *adjList[NUM_VERTICES] = {NULL}; // 图的邻接表// 初始化图并添加边// 示例: addEdge(adjList, 0, 1); // 添加一条从顶点 0 到顶点 1 的边int startVertex = 0; // 起始顶点unweighted(vertices, adjList, startVertex);// 打印结果或按需使用for (int i = 0; i < NUM_VERTICES; i++) {printf("顶点 %d: 距离 = %d, 前驱 = %d\n", i, vertices[i].dist, vertices[i].path);}return 0;
}void unweighted(Vertex *vertices, Edge *adjList[], int s) {// 初始化所有顶点for (int i = 0; i < NUM_VERTICES; i++) {vertices[i].dist = INT_MAX; // 初始距离设为无穷大vertices[i].known = 0;      // 初始状态为未知vertices[i].path = -1;      // 初始前驱顶点为 -1}// 设置起始顶点的距离为 0vertices[s].dist = 0;// 按照距离递增的顺序处理顶点for (int currDist = 0; currDist < NUM_VERTICES; currDist++) {for (int i = 0; i < NUM_VERTICES; i++) {if (!vertices[i].known && vertices[i].dist == currDist) {vertices[i].known = 1; // 标记顶点为已知// 更新相邻顶点的距离for (Edge *e = adjList[i]; e != NULL; e = e->next) {int w = e->dest;if (vertices[w].dist == INT_MAX) {vertices[w].dist = currDist + 1; // 更新距离vertices[w].path = i;            // 更新前驱顶点}}}}}
}void addEdge(Edge *adjList[], int src, int dest) {Edge *newEdge = (Edge *)malloc(sizeof(Edge)); // 分配新边的内存newEdge->dest = dest;                          // 设置目标顶点newEdge->next = adjList[src];                 // 将新边插入到邻接表头部adjList[src] = newEdge;                       // 更新邻接表
}

Vertex 结构体：表示图中的顶点，包含距离 (dist)、是否已知 (known) 和前驱顶点 (path)。
Edge 结构体：表示图中的边，包含目标顶点索引 (dest) 和指向下一个边的指针 (next)。
unweighted 函数：实现无权图的单源最短路径算法。
addEdge 函数：向图中添加边。
main 函数：初始化图并调用 unweighted 函数计算从起始顶点到其他所有顶点的最短路径，然后打印结果。

2. Dijkstra算法

Dijkstra算法用于解决有权图中的单源最短路径问题。该算法通过维护一个优先队列来选择当前距离最小的未访问节点作为下一个访问节点，从而逐步构建从源节点到其他所有节点的最短路径树。

Dijkstra 算法按阶段进行，正像无权最短路径算法一样。在每个阶段，Dijkstra 算法选择一个顶点 v，它在所有 unknown 顶点中具有最小的 dv，同时算法声明从 s 到 v 的最短路径是 known 的。阶段的其余部分由 dw 值的更新工作组成。

Dijkstra算法原理

初始化：
- 将源节点的距离设为0，其他所有节点的距离设为无穷大。
- 创建一个集合来记录已经确定最短路径的节点。
迭代过程：
- 从尚未确定最短路径的节点中选择一个距离最小的节点，标记为已确定最短路径。
- 更新该节点的所有邻居节点的距离。如果通过当前节点到达邻居节点的距离比已知的距离更短，则更新邻居节点的距离和前驱节点。
终止条件：
- 当所有节点都已确定最短路径时，算法结束。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 包含 INT_MAX，等同于无穷大#define NUM_VERTICES 100 // 定义图中的顶点数量typedef struct {int dist;       // 从源顶点的距离int known;      // 是否已经确定最短路径int path;       // 路径上的前驱顶点
} Vertex;// 邻接矩阵表示图
int graph[NUM_VERTICES][NUM_VERTICES];// 初始化图
void initializeGraph(int n) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) {graph[i][j] = 0; // 自环距离为0} else {graph[i][j] = INT_MAX; // 未连接的边距离设为无穷大}}}
}// 添加边
void addEdge(int u, int v, int weight) {graph[u][v] = weight;// 如果是无向图，还需要添加反向边// graph[v][u] = weight;
}// Dijkstra算法
void dijkstra(Vertex *vertices, int n, int start) {// 初始化所有顶点for (int i = 0; i < n; i++) {vertices[i].dist = INT_MAX; // 初始距离设为无穷大vertices[i].known = 0;      // 初始状态为未知vertices[i].path = -1;      // 初始前驱顶点为 -1}// 设置起始顶点的距离为 0vertices[start].dist = 0;// 主循环：直到所有顶点都已确定最短路径while (1) {int minDist = INT_MAX;int u = -1;// 选择一个距离最小且未确定最短路径的顶点for (int i = 0; i < n; i++) {if (!vertices[i].known && vertices[i].dist < minDist) {minDist = vertices[i].dist;u = i;}}// 如果找不到这样的顶点，算法结束if (u == -1) {break;}// 标记该顶点为已确定最短路径vertices[u].known = 1;// 更新该顶点的所有邻居节点的距离for (int v = 0; v < n; v++) {if (graph[u][v] != INT_MAX && !vertices[v].known) { // 如果存在边且邻居节点未确定最短路径int newDist = vertices[u].dist + graph[u][v];if (newDist < vertices[v].dist) {vertices[v].dist = newDist; // 更新距离vertices[v].path = u;       // 更新前驱顶点}}}}
}// 打印最短路径
void printShortestPaths(Vertex *vertices, int n, int start) {for (int i = 0; i < n; i++) {if (i == start) {continue; // 跳过起始顶点}printf("从顶点 %d 到顶点 %d 的最短路径为: ", start, i);if (vertices[i].dist == INT_MAX) {printf("不可达\n");} else {printf("%d ", vertices[i].dist);int path = i;while (path != -1) {printf("%d <- ", path);path = vertices[path].path;}printf("\b\b\b\n"); // 删除最后一个 "<-"}}
}int main() {int n = 5; // 顶点数量initializeGraph(n); // 初始化图// 添加边addEdge(0, 1, 10);addEdge(0, 4, 5);addEdge(1, 2, 1);addEdge(1, 4, 2);addEdge(2, 3, 4);addEdge(3, 2, 6);addEdge(4, 1, 3);addEdge(4, 2, 9);addEdge(4, 3, 2);Vertex vertices[n];int startVertex = 0; // 起始顶点dijkstra(vertices, n, startVertex); // 计算最短路径printShortestPaths(vertices, n, startVertex); // 打印最短路径return 0;
}

代码分析

初始化图：
- initializeGraph 函数将图初始化为一个邻接矩阵，其中对角线元素为0（表示自环），其他元素为 INT_MAX（表示无穷大）。
添加边：
- addEdge 函数用于向图中添加边。对于有向图，只需设置 graph[u][v]；对于无向图，还需设置 graph[v][u]。
Dijkstra算法：
- dijkstra 函数实现Dijkstra算法。
- 初始化所有顶点的距离为 INT_MAX，已知状态为 0，前驱顶点为 -1。
- 将起始顶点的距离设为0。
- 在主循环中，选择一个距离最小且未确定最短路径的顶点，标记为已确定最短路径。
- 更新该顶点的所有邻居节点的距离，如果通过当前顶点到达邻居节点的距离更短，则更新邻居节点的距离和前驱顶点。
打印最短路径：
- printShortestPaths 函数用于打印从起始顶点到其他所有顶点的最短路径及其路径信息。

运行示例

假设图中有5个顶点，边的权重如下：

(0, 1): 10
(0, 4): 5
(1, 2): 1
(1, 4): 2
(2, 3): 4
(3, 2): 6
(4, 1): 3
(4, 2): 9
(4, 3): 2

运行程序后，输出如下：

从顶点 0 到顶点 1 的最短路径为: 8 1 <- 4 <- 0
从顶点 0 到顶点 2 的最短路径为: 9 2 <- 1 <- 4 <- 0
从顶点 0 到顶点 3 的最短路径为: 7 3 <- 4 <- 0
从顶点 0 到顶点 4 的最短路径为: 5 4 <- 0

3. 所有顶点对间的最短路径

有时需要找出图中所有顶点之间的最短路径，这可以运行 |V| 次适当的单源(single-source) 算法，但对于稠密图，还是应该用更快些的算法。
之后会给出对赋权图求解这种问题的一个 O(|V|3) 算法。虽然对于稠密图它具有和运行 |V| 次简单（非-优先队列）Dijkstra 算法相同的时间界，但它循环非常紧凑，以至于这种专业化的所有顶点对算法很可能在实践中更快。当然，对于稀疏图，更快的是运行 |V| 次用优先队列编码的 Dijkstra 算法。

4. 最短路径的例子1

思考以下问题：使用C++ 来计算词梯游戏(word ladder)。在一个词梯中，每个单词均由其前面的单词改变一个字母而得到。例如，可以通过一系列单字母替换而将 zero 转换为 five：zero hero here hire five。
这是一个无权最短路径问题，其中每一个单词都是一个顶点，如果两个单词可以通过单字母替换而相互转换，那么它们之间就有边存在（双向）。

该例程创建一个map，其关键字是单词，相应的值是包含从单字母变换得到的那些单词的vector 对象。即，这个 map 代表一个以邻接表格式表示的图。

//求词梯的C++ 例程
//从邻接映射（adjacency map) 进行最短路径计算，返回一个向量
//该向量包含从first 到second 得到的单词相继变化
unordered_map<string,string>
findChain(const unordered_map<string, vector<string>>& adjacentWords,const string& first, const string& second)
{unordered_map<string, string> previousWord;queue<string>q;q.push(first);while (!q.empty()){string current = q.front();q.pop();auto itr = adjacentWords.find(current);const vector<string>& adj = itr->second;for(const string&str:adj)if (previousWord[str] == ""){previousWord[str] = current;q.push(str);}}previousWord[first] = "";return previousWord;
}//在最短路径计算运行之后，计算包含从first 到second 得到的
//单词相继变化的vector 对象
vector<string> getChainFromPreviousMap(const unordered_map<string, string>& previous, const string& second)
{vector<string>result;auto& prev = const_cast<unordered_map<string, string>&>(previous);for (string current = second; current != ""; current = prev[current])result.push_back(current);reverse(begin(result), end(result));return result;
}

4. 最短路径的例子2

假设我们有一个有向图，包含5个节点（A, B, C, D, E），各边之间的权重如下所示：

A -> B: 1
A -> C: 4
B -> C: 1
B -> D: 2
C -> E: 3
D -> E: 1

我们的目标是找到从节点A到所有其他节点的最短路径。

解决方案

1. 数据结构

为了实现Dijkstra算法，我们需要几个数据结构：

distance[]：存储从起始节点到每个节点的最短距离。
visited[]：标记节点是否已被访问过。
parent[]：记录最短路径上的前驱节点，以便于回溯路径。

2. 算法步骤

初始化distance[]数组为无穷大，除了起始节点的距离为0。
初始化visited[]数组为false。
创建一个优先队列（或使用简单的数组），按照距离从小到大的顺序存储未访问的节点。
当优先队列非空时：
- 从队列中取出距离最小的节点u。
- 对于节点u的所有邻接节点v，如果通过u到达v的距离小于当前已知的最短距离，则更新v的最短距离，并将v加入优先队列。
重复上述过程直到优先队列为空。

#include <stdio.h>
#include <limits.h>#define V 5 // 节点数量// 选择距离最近且未访问的节点
int minDistance(int dist[], int visited[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++)if (!visited[v] && dist[v] <= min)min = dist[v], min_index = v;return min_index;
}void dijkstra(int graph[V][V], int src) {int dist[V]; // 存储最短距离int visited[V]; // 标记节点是否已被访问int parent[V]; // 记录最短路径上的前驱节点// 初始化for (int i = 0; i < V; i++) {dist[i] = INT_MAX;visited[i] = 0;parent[i] = -1;}dist[src] = 0;// 找到最短路径for (int count = 0; count < V - 1; count++) {int u = minDistance(dist, visited);visited[u] = 1;for (int v = 0; v < V; v++)if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {parent[v] = u;dist[v] = dist[u] + graph[u][v];}}// 打印结果printf("Vertex\tDistance from Source\n");for (int i = 0; i < V; i++)printf("%d \t\t %d\n", i, dist[i]);
}int main() {int graph[V][V] = { {0, 1, 4, 0, 0},{0, 0, 1, 2, 0},{0, 0, 0, 0, 3},{0, 0, 0, 0, 1},{0, 0, 0, 0, 0} };dijkstra(graph, 0);return 0;
}