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

前面介绍了图的应用——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)—用边表示活动的网络,对应关键路径算法

比如教学计划的制定

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

813a3be2128d421087bfe1658d8d3572.png

38b2742be8b1426ca253d0ca2274dcdc.png

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 

31b26f9a550947cd8d581d01f5a8da5e.png

三,关键路径

        用途:估算工程项目完成时间

        AOE网络:定义结点为事件,有向边的指向表示事件的执行次序。单位是时间(时刻)。有向边定义为活动,它的权值定义为活动进行所需要的时间。

8045c414e31348acb08fb1e8ac408c2b.png

5c892b536ebb4c79a1ef8d598ab61265.png

•   术语:

    源点:表示整个工程的开始点,也称起点(入度为0)。

    收点:表示整个工程的结束点,也称汇点(出度为0)。

9fe1fbecdbd8420cbab322544928daee.png

求解关键路径,我们还需要知道以下概念: 

f3f8def6bf304836b8d878302ebc4b2a.png

 那么该如何求这些值?6ffb4656b9894b47a12741dcb808540c.png

     Ve(j) 及 Vl(j))的求法:

7a9e67218b7e42c1b8517ed568c5294f.png

 我们可以看出,关键路径就是通过加总最长路径上所有活动的持续时间来确定的项目最短完成时间。

下面是另一个例子

991655bc1e2941a39241dcb4ba6e19bf.png

995703f57952446a9c943c09071ca501.png

4dc397c367da41c8a924934b19f1497b.png

因此我们就求出了此活动的关键路径

242c9bfb467749ff90746707f33a02c7.png


图的应用章节就到此结束啦,不知道大家有没有掌握呢?

如果文章对你有用的话请点个赞支持一下吧!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3245312.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

整数或小数点后补0操作

效果展示&#xff1a; 整数情况&#xff1a; 小数情况&#xff1a; 小编这里是以微信小程序举例&#xff0c;代码通用可兼容vue等。 1.在utils文件下创建工具util.js文本 util.js页面&#xff1a; // 格式…

React@16.x(60)Redux@4.x(9)- 实现 applyMiddleware

目录 1&#xff0c;applyMiddleware 原理2&#xff0c;实现2.1&#xff0c;applyMiddleware2.1.1&#xff0c;compose 方法2.1.2&#xff0c;applyMiddleware 2.2&#xff0c;修改 createStore 接上篇文章&#xff1a;Redux中间件介绍。 1&#xff0c;applyMiddleware 原理 R…

【精品资料】大数据可视化平台数据治理方案(626页WORD)

引言&#xff1a;大数据可视化平台的数据治理方案是一个综合性的策略&#xff0c;旨在确保大数据的质量、安全性、可访问性和合规性&#xff0c;从而支持高效的数据分析和可视化过程。 方案介绍&#xff1a; 大数据可视化平台的数据治理方案是一个综合性的策略&#xff0c;旨在…

Nginx源码windows下编译

参考&#xff1a;Nginx Windows下编译和安装_window 如果编译安装nginx-CSDN博客 参考&#xff1a; Building nginx on the Win32 platform with Visual C 1.安装MSYS2 参考 MSYS2 下 installation 内容下载安装即可。 2.下载依赖库&#xff1a; PCRE:Download PCRE ​ …

在设计电气系统时,电气工程师需要考虑哪些关键因素?

在设计电气系统时&#xff0c;电气工程师需要考虑多个关键因素&#xff0c;以确保系统的安全性、可靠性、效率和经济性。我收集归类了一份plc学习包&#xff0c;对于新手而言简直不要太棒&#xff0c;里面包括了新手各个时期的学习方向编程教学、问题视频讲解、毕设800套和语言…

三球交汇定理计算标签位置(UWB)

目录 题目三球交汇定理计算过程代码实现说明 题目 假设标签坐标为(x0,y0)&#xff0c;基站ABCD的坐标分别为(x1,y1)(x2,y2)(x3,y3)(x4,y4)&#xff0c;基站坐标已知&#xff0c;如何计算标签坐标&#xff1f; 三球交汇定理 三球交汇定位&#xff08; Three-ball intersection…

SAP PP学习笔记28 - 生产订单的收货及品质管理

上一章讲了生产订单的很多概念&#xff0c;比如确认&#xff08;报工&#xff09;以及报工的各种形式&#xff0c;反冲&#xff0c;自动入库等。 SAP PP学习笔记27 - Confirmation(报工/确认&#xff09;(CO11&#xff0c;CO11N&#xff0c;CO15&#xff0c;CO12)&#xff0c;…

【排序算法】1.冒泡排序-C语言实现

冒泡排序&#xff08;Bubble Sort&#xff09;是最简单和最通用的排序方法&#xff0c;其基本思想是&#xff1a;在待排序的一组数中&#xff0c;将相邻的两个数进行比较&#xff0c;若前面的数比后面的数大就交换两数&#xff0c;否则不交换&#xff1b;如此下去&#xff0c;直…

ospf复习综合小实验

实验要求&#xff1a; 1&#xff0c;R4为ISP&#xff0c;其上只能配置IP地址&#xff1b;R4与其他所有直连设备间均使用公有IP 2&#xff0c;R3-R5/6/7为MGRE环境&#xff0c;R3为中心站点&#xff1b; 3&#xff0c;整个OSPF环境IP基于172.16.0.0/16划分&#xff1b; 4&#…

Pytorch学习笔记day1—— 安装教程

这里写自定义目录标题 Pytorch安装方式 工作需要&#xff0c;最近开始搞一点AI的事情。但是这个国产的AI框架&#xff0c;实话说对初学者不太友好 https://www.mindspore.cn/ 比如说它不支持win下的CUDA&#xff0c;可是我手里只有3070Ti和4060也不太可能自己去买昇腾就有点绷不…

读人工智能全传15意向立场

1. 物理立场 1.1. 可以解释一个实体行为 1.2. 在物理立场中&#xff0c;我们使用自然法则(物理、化学等)来预测系统的行为结果 1.3. 虽然物理立场在解释这种行为的时候非常有效&#xff0c;但无法应用于理解或者预测人类行为 1.3.1. …

0601大学物理电磁篇 静电场中的导体和电介质

静电场中的导体和电介质01 6-1静电场中的导体 6-1静电场中的导体

【Java--数据结构】二叉树

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 树结构 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合 注意&#xff1a;树形结构中&#xff0c;子…

Qt实现IP地址输入框-自定义控件

在 许多应用程序中&#xff0c;我们经常需要使用IP地址。为了方便用户输入和处理&#xff0c;一个好的解决方案是使用自定义控件。本示例代码使用Qt编写一个名为“IPAddress”的自定义控件来实现IP地址的输入功能。通过使用此控件&#xff0c;用户可以方便地输入和处理IP地址。…

【中项第三版】系统集成项目管理工程师 | 第 5 章 软件工程② | 5.4 - 5.8

前言 第 5 章对应的内容选择题和案例分析都会进行考查&#xff0c;这一章节属于技术的内容&#xff0c;学习要以教材为准。 目录 5.4 软件实现 5.4.1 软件配置管理 5.4.2 软件编码 5.4.3 软件测试 5.5 部署交付 5.5.1 软件部署 5.5.2 软件交付 5.5.3 持续交付 5.5.4…

全新升级!联想Windows 10 22H2专业版,一键下载!

联想Windows 10 22H2专业版系统适用于联想笔记本、台式机安装使用&#xff0c;全新优化升级&#xff0c;运作更流畅更稳定&#xff0c;丰富多样的系统功能&#xff0c;轻松满足用户日常学习、工作的使用需求。同时&#xff0c;该版本系统能够正常更新补丁&#xff0c;您也可以手…

useState函数

seState是一个react Hook(函数)&#xff0c;它允许我们像组件添加一个状态变量&#xff0c;从而控制影响组件的渲染结果 数据驱动试图 本质&#xff1a;和普通JS变量不同的是&#xff0c;状态变量一旦发生变化组件的视图UI也会随着变化(数据驱动试图) 使用 修改状态 注意&am…

LabVIEW异步和同步通信详细分析及比较

1. 基本原理 异步通信&#xff1a; 原理&#xff1a;异步通信&#xff08;Asynchronous Communication&#xff09;是一种数据传输方式&#xff0c;其中数据发送和接收操作在独立的时间进行&#xff0c;不需要在特定时刻对齐。发送方在任何时刻可以发送数据&#xff0c;而接收…

Java猿社区—理解Java中的字符串比较机制

Java中的字符串比较是一个经典且常见的问题&#xff0c;尤其是在面试中。本文将详细探讨通过三种不同方式创建的字符串对象之间的比较机制&#xff0c;并扩展相关的技术问题&#xff0c;帮助读者深入理解Java的字符串处理。 文章目录 1. Java中的字符串对象创建方式2. 和equals…

在AWS创建一台Windows主机并登录

正文共&#xff1a;1111 字 21 图&#xff0c;预估阅读时间&#xff1a;1 分钟 因为之前微软云Azure免费&#xff0c;我们还做了简单的测试&#xff08;白嫖党618福利&#xff01;来Azure领200美刀&#xff01;外加云主机免费用一年&#xff01;&#xff09;&#xff1b;并且通…