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

🕗 发布于 2024-11-15 01:47 c 图论算法 c语言 性能优化

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

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

在图论中，最短路径问题是寻找图中两点之间具有最小总权重的路径。这个问题在许多实际应用中都有重要的作用，比如网络路由、城市交通规划等。本文将探讨几种不同的最短路径算法，包括无权最短路径、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 1000000

typedef 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开始BFS

    return 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
    }

    // 设置起始顶点的距离为 0
    vertices[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
    }

    // 设置起始顶点的距离为 0
    vertices[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;
}

minDistance 函数用于寻找当前未被访问过的节点中距离最小的一个。
dijkstra 函数实现了Dijkstra算法的核心逻辑。
在主函数中，定义了一个图的邻接矩阵表示，并调用了dijkstra函数以0作为源节点开始计算最短路径。

输出了从源节点0到其他所有节点的最短距离。通过调整邻接矩阵和源节点，可以应用于不同的图和起点

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

原文地址：https://blog.csdn.net/Asuna666w/article/details/143782874

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Flutter网络通信-封装Dio
下一篇：scala创建图书信息类，包含三个属性：书名，作者，价格

单片机和FPGA有什么区别？
总的来说，选择单片机还是FPGA取决于具体的应用需求、成本预算、开发资源和性能要求。单片机更适合成本敏感和性能要求不高的应用，而FPGA则适用于需要高度定制化和高性能的应用。
阅读更多2024-11-15
离线语音识别自定义功能怎么用？
自学习功能是指终端用户可以通过语音输入的方式学习客户词条，来自定义唤醒词和命令词。设备默认可以通过“开灯”执行打开灯的动作，用户通过语音输入学习了“开一下灯”，则可以通过“开一下灯”的说法来执行打开灯
阅读更多2024-11-15
PPT技巧：如何合并PPT文件？
如何合并PPT文件？
阅读更多2024-11-15
Unity3D高级编程
本文是unity3d编程的核心内容，包括了多个知识点以及C#代码实现
阅读更多2024-11-15
HOW - PPT 制作系列（一）
注意以上几点，可以让一页PPT既美观又高效地传达信息。
阅读更多2024-11-15
不仅能够实现前后场的简单互动，而且能够实现人机结合，最终实现整个巡检流程的标准化的智慧园区开源了
智慧园区场景视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒，省去繁琐重复的适配流程，实现芯片、算法、应用的全流程组合，从而大大减少企业级应用约
阅读更多2024-11-15
云原生后端
一、背景与概念二、关键技术三、优势四、应用场景
阅读更多2024-11-15
云原生学习
云原生学习：介绍、Docker容器化
阅读更多2024-11-15
气膜球幕展览馆：开启元宇宙时代的沉浸式科技体验—轻空间
球幕结构能够包裹观众的全部视野，在这里，每一幅画面都经过精心调校，色彩真实、细节丰富，使得场景的还原度达到一个全新的高度。这样独特的沉浸感，是传统展览馆所无法比拟的，气膜球幕展览馆让每一位参观者都仿佛
阅读更多2024-11-15
Istio分布式链路监控搭建：Jaeger与Zipkin
Jaeger是由Uber开源的分布式追踪系统，它采用Go语言编写，主要借鉴了Google Dapper论文和Zipkin的设计，兼容OpenTracing以及Zipkin追踪格式，目前已经成为CNCF
阅读更多2024-11-15

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