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

图——图的应用02最短路径（Dijkstra算法与Floyd算法详解），拓扑排序及关键路径

news 来源：原创 2024/9/19 15:32:38

前面介绍了图的应用——01最小生成树章节，大家可以通过下面的链接学习：

图——图的应用01最小生成树（Prim算法与Kruskal算法详解）

今天就讲一下图的其他应用——最短路径，拓扑排序及关键路径。

一，最短路径

1，Dijkstra（迪杰斯特拉）算法

Dijkstra算法思想

c语言中Dijkstra算法的完整代码：

2， Floyd（弗洛伊德）算法

Floyd算法思想：

c语言中Floyd算法的完整代码：

二，拓扑排序

三，关键路径

一，最短路径

两种常见的最短路径问题：

一、单源最短路径—用Dijkstra（迪杰斯特拉）算法

二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法

1，Dijkstra（迪杰斯特拉）算法

Dijkstra算法思想

1.初始化：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。

2.选择：从这些路径中找出一条长度最短的路径（v0,u）。

3.更新：然后对其余各条路径进行适当调整，即：

从v0到其余各点的最短路径--按路径长度递增次序求解

1、把V分成两组：

(1) S：已求出最短路径的顶点的集合。

(2) T=V -S：尚未确定最短路径的顶点集合。

2、将T中顶点按最短路径递增的次序加入到S中，

保证：

(1)从源点v0到S中各顶点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度。

(2)每个顶点对应一个距离值：

S中顶点：从v0到此顶点的最短路径长度。

T中顶点：从v到此顶点的只包括S中顶点作中间顶点的最短路径长度。

下面是一个实例——

c语言中Dijkstra算法的完整代码：

#include <stdio.h>
#include <limits.h>#define V 9// 函数minDistance用于找到距离源节点最近的节点
int minDistance(int dist[], int sptSet[]) {int min = INT_MAX, min_index;// 遍历所有节点，找到距离源节点最近的节点for (int v = 0; v < V; v++)if (sptSet[v] == 0 && dist[v] <= min)min = dist[v], min_index = v;return min_index;
}// 函数printSolution用于打印最短路径
void printSolution(int dist[]) {printf("Vertex \t\t Distance from Source");// 遍历所有节点，打印最短路径for (int i = 0; i < V; i++)printf("%d \t\t %d", i, dist[i]);
}// 函数dijkstra用于计算最短路径
void dijkstra(int graph[V][V], int src) {int dist[V];int sptSet[V];// 初始化距离数组和最短路径集合for (int i = 0; i < V; i++)dist[i] = INT_MAX, sptSet[i] = 0;dist[src] = 0;// 遍历所有节点，计算最短路径for (int count = 0; count < V - 1; count++) {int u = minDistance(dist, sptSet);sptSet[u] = 1;// 更新距离数组for (int v = 0; v < V; v++)if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])dist[v] = dist[u] + graph[u][v];}printSolution(dist);
}int main() {int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};dijkstra(graph, 0);return 0;
}

结果如下：

Vertex    Distance from Source
0    0
1    4
2    12
3    19
4    21
5    11
6    9
7    8
8    14

2， Floyd（弗洛伊德）算法

求所有顶点间的最短路径有两种方法：

方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次。

方法二：弗洛伊德(Floyd)算法。

Floyd算法思想：

1、逐个顶点试探；

2、从𝑣𝑖v_i到𝑣𝑗v_j的所有可能存在的路径中

3、选出一条长度最短的路径

c语言中Floyd算法的完整代码：

与之前同样使用了“limits”库， "INF"表示两个顶点之间没有路径。使用INT_MAX来表示无穷大，当两个顶点之间没有直接路径时，它们的距离就是无穷大。

#include <stdio.h>
#include <limits.h>#define V 4// 打印最短路径矩阵
void printSolution(int dist[][V]);// Floyd-Warshall算法
void floydWarshall(int graph[][V]) {int dist[V][V], i, j, k;// 初始化距离矩阵for (i = 0; i < V; i++)for (j = 0; j < V; j++)dist[i][j] = graph[i][j];// 三重循环，计算最短路径for (k = 0; k < V; k++) {for (i = 0; i < V; i++) {for (j = 0; j < V; j++) {if (dist[i][k] + dist[k][j] < dist[i][j])dist[i][j] = dist[i][k] + dist[k][j];}}}// 打印最短路径矩阵printSolution(dist);
}// 打印最短路径矩阵
void printSolution(int dist[][V]) {printf("以下是最短路径矩阵：");for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {if (dist[i][j] == INT_MAX)printf("%7s", "INF");elseprintf("%7d", dist[i][j]);}printf(" \n");}
}int main() {int graph[V][V] = {{0, 5, INT_MAX, 10},{INT_MAX, 0, 3, INT_MAX},{INT_MAX, INT_MAX, 0, 1},{INT_MAX, INT_MAX, INT_MAX, 0}};// 调用Floyd-Warshall算法floydWarshall(graph);return 0;
}

输出结果：

以下是最短路径矩阵：
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0

二，拓扑排序

首先我们需要知道拓扑排序是针对有向无环图（DAG）的，在实例中，我们经常用有向图来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成。

表示活动有两种方式：

① AOV网(Activity On Vertices)—用顶点表示活动的网络，对应拓扑排序算法

② AOE网(Activity On Edges)—用边表示活动的网络，对应关键路径算法

比如教学计划的制定

哪些课程是必须先修的，哪些课程是可以并行学习的

AOV网特点

1.若从顶点Vi到顶点Vj有路径（有向边），则Vi 是Vj 的（直接）前驱； Vj 是Vi 的（直接）后继。

2.AOV网不能存在回路。

3.拓扑排序，所有顶点排成一个线性序列。

无环有向图的判断方法：若网中顶点都在拓扑有序序列中，则AOV-网。不存在环。

拓扑排序算法的思想：重复选择没有直接前驱的顶点。

具体步骤如下：

1.输入AOV网络。令 n 为顶点个数。

2.在AOV网络中选一个没有直接前驱的顶点, 并输出之;

3.从图中删去该顶点, 同时删去所有它发出的有向边;

重复以上 2、3 步, 直到：

         全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；

         或：

        图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。

我们仍以教学计划的制定为例分析此过程：

•对学生选课工程图进行拓扑排序，得到的拓扑有序序列为

C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7

或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6