图&网络模型应用：最短路问题、 Dijkstra算法、Floyd算法

您所在的位置：网站首页 › 最短路问题的数学模型论文 › 图&网络模型应用：最短路问题、 Dijkstra算法、Floyd算法

图&网络模型应用：最短路问题、 Dijkstra算法、Floyd算法

2024-04-05 10:57| 来源: 网络整理| 查看: 265

图&网络系列博文：

【1】图与网络模型及方法：图与网络的基本概念

【2】图&网络模型应用—最短路径问题

【3】树：基本概念与最小生成树

【4】匹配问题：匈牙利算法、最优指派、相等子图

【5】Euler 图和 Hamilton 图

【6】计划评审方法和关键路线法【统筹方法】：广泛地用于系统分析和项目管理

【7】最小费用流及其求法：

【8】最大流问题

【9】钢管订购和运输问题

1 两个指定顶点之间的最短路径 Dijkstra算法

2 两个指定顶点之间最短路问题的数学表达式

例 2 最小价格管道铺设方案例3 （无向图的最短路问题）

3 每对顶点之间的最短路径 Floyd算法

1 两个指定顶点之间的最短路径

问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。

Dijkstra算法

例1 某公司在六个城市 $c_{1},c_{2},...,c_{6}$ 中有分公司，从 $c_{i}$ 到 $c_{j}$ 的直接航程票价记在如下矩阵的 $\left ( i,j \right )$ 位置上。（∞表示无直接航路），请帮助该公司设计一张城市 $c_{1}$ 到其它城市间的票价便宜的路线图。

解用矩阵 $a_{n\times n}$ （n为顶点个数）存放各边权的邻接矩阵，行向量 $pb, index_{1} , index_{2} , d$ 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、短通路的值。其中分量

求第一个城市到其它城市的短路径的 Matlab 程序如下：

clc,clear a=zeros(6); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; a(find(a==0))=inf; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0;temp=1; while sum(pb)

【本文地址】

图&网络模型应用：最短路问题、 Dijkstra算法、Floyd算法

图&网络模型应用：最短路问题、 Dijkstra算法、Floyd算法

今日新闻

推荐新闻

图&网络模型应用：最短路问题、 Dijkstra算法 、Floyd算法

图&网络模型应用：最短路问题、 Dijkstra算法 、Floyd算法

今日新闻

推荐新闻

图&网络模型应用：最短路问题、 Dijkstra算法、Floyd算法

图&网络模型应用：最短路问题、 Dijkstra算法、Floyd算法