数模 03图论Dijkstra and Floyd matlab 及 软件使用

使用解题软件辅助，如MATLAB或Excel #生活技巧# #学习技巧# #解题技巧训练#

Dijkstra算法

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

此算法求的是两点间的最短路径，注意，得先画出带权邻接矩阵：

[0 2 8 1 Inf Inf Inf Inf Inf Inf Inf;

2 0 6 Inf 1 Inf Inf Inf Inf Inf Inf;

8 6 0 7 5 1 2 Inf Inf Inf Inf;

1 Inf 7 0 Inf Inf 9 Inf Inf Inf Inf;

Inf 1 5 Inf 0 3 Inf 2 9 Inf Inf;

Inf Inf 1 Inf 3 0 4 Inf 6 Inf Inf;

Inf Inf 2 9 Inf 4 0 Inf 3 1 Inf;

Inf Inf Inf Inf 2 Inf Inf 0 7 Inf 9;

Inf Inf Inf Inf 9 6 3 7 0 1 2;

Inf Inf Inf Inf Inf Inf 1 Inf 1 0 4;

Inf Inf Inf Inf Inf Inf Inf 9 2 4 0;]

[0 8 Inf Inf Inf Inf 7 8 Inf Inf Inf;

Inf 0 3 Inf Inf Inf Inf Inf Inf Inf Inf;

Inf Inf 0 5 6 Inf 5 Inf Inf Inf Inf;

Inf Inf Inf 0 1 Inf Inf Inf Inf Inf 12;

Inf Inf 6 Inf 0 2 Inf Inf Inf Inf 10;

Inf Inf Inf Inf 2 0 9 Inf 3 Inf Inf;

Inf Inf Inf Inf Inf 9 0 Inf Inf Inf Inf;

8 Inf Inf Inf Inf Inf Inf 0 9 Inf Inf;

Inf Inf Inf Inf 7 Inf Inf 9 0 2 Inf;

Inf Inf Inf Inf Inf Inf Inf Inf 2 0 2;

Inf Inf Inf Inf 10 Inf Inf Inf Inf Inf 0;];

至于具体算法在数据结构课程中已经了解到了，下面直接给出matlab实操过程。

主程序

weight= [0 2 8 1 Inf Inf Inf Inf Inf Inf Inf;

2 0 6 Inf 1 Inf Inf Inf Inf Inf Inf;

8 6 0 7 5 1 2 Inf Inf Inf Inf;

1 Inf 7 0 Inf Inf 9 Inf Inf Inf Inf;

Inf 1 5 Inf 0 3 Inf 2 9 Inf Inf;

Inf Inf 1 Inf 3 0 4 Inf 6 Inf Inf;

Inf Inf 2 9 Inf 4 0 Inf 3 1 Inf;

Inf Inf Inf Inf 2 Inf Inf 0 7 Inf 9;

Inf Inf Inf Inf 9 6 3 7 0 1 2;

Inf Inf Inf Inf Inf Inf 1 Inf 1 0 4;

Inf Inf Inf Inf Inf Inf Inf 9 2 4 0;];

[dis, path]=dijkstra(weight,1, 11)

在主程序中的weight即为需要自行填写的带权邻接矩阵，dijkstra(weight,1, 11)表示求的是1到11的最短路径

迪杰斯特拉算法程序

function [min,path]=dijkstra(w,start,terminal)

n=size(w,1); label(start)=0; f(start)=start;

for i=1:n

if i~=start

label(i)=inf;

end, end

s(1)=start; u=start;

while length(s)<n

for i=1:n

ins=0;

for j=1:length(s)

if i==s(j)

ins=1;

end,

end

if ins==0

v=i;

if label(v)>(label(u)+w(u,v))

label(v)=(label(u)+w(u,v));

f(v)=u;

end,

end,

end

v1=0;

k=inf;

for i=1:n

ins=0;

for j=1:length(s)

if i==s(j)

ins=1;

end,

end

if ins==0

v=i;

if k>label(v)

k=label(v); v1=v;

end,

end,

end

s(length(s)+1)=v1;

u=v1;

end

min=label(terminal); path(1)=terminal;

i=1;

while path(i)~=start

path(i+1)=f(path(i));

i=i+1 ;

end

path(i)=start;

L=length(path);

path=path(L:-1:1);

然后在命令行输入主程序保存的文件名，这里我保存的是tulun1，输出：

 dis为最短路径长度，path表示最短路径经过的点。

Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

直接程序加使用方法吧，在数据结构里面学过了，算法过程不再赘述

matlab主程序

a= [ 0,50,inf,40,25,10;

50,0,15,20,inf,25;

inf,15,0,10,20,inf;

40,20,10,0,10,25;

25,inf,20,10,0,55;

10,25,inf,25,55,0];

[D, path]=floyd(a)

floyd算法程序

function [D,path,min1,path1]=floyd(a,start,terminal)

D=a;n=size(D,1);path=zeros(n,n);

for i=1:n

for j=1:n

if D(i,j)~=inf

path(i,j)=j;

end,

end,

end

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j)<D(i,j)

D(i,j)=D(i,k)+D(k,j);

path(i,j)=path(i,k);

end,

end,

end,

end

if nargin==3

min1=D(start,terminal);

m(1)=start;

i=1;

path1=[ ];

while path(m(i),terminal)~=terminal

k=i+1;

m(k)=path(m(i),terminal);

i=i+1;

end

m(i+1)=terminal;

path1=m;

end

举例的话用另外一个举例吧：

[0 8 Inf Inf Inf Inf 7 8 Inf Inf Inf;

Inf 0 3 Inf Inf Inf Inf Inf Inf Inf Inf;

Inf Inf 0 5 6 Inf 5 Inf Inf Inf Inf;

Inf Inf Inf 0 1 Inf Inf Inf Inf Inf 12;

Inf Inf 6 Inf 0 2 Inf Inf Inf Inf 10;

Inf Inf Inf Inf 2 0 9 Inf 3 Inf Inf;

Inf Inf Inf Inf Inf 9 0 Inf Inf Inf Inf;

Inf Inf Inf Inf Inf Inf 0 9 Inf Inf;

Inf Inf Inf Inf 7 Inf Inf 9 0 2 Inf;

Inf Inf Inf Inf Inf Inf Inf Inf 2 0 2;

Inf Inf Inf Inf 10 Inf Inf Inf Inf Inf 0;];

输出：

其中如果要找1到11的，先找path的（1，11）显示为8，所以找（8，11）显示为9，找（9，11）为10.。。。最后得到最短路径为1，8，9，10，11。距离分别将d矩阵相应数值加起来即可。

下面利用上面的知识，迪杰斯特拉算法验证结果

结果相同。

图论软件操作

ps：需要软件请留言

进入软件：

随机画上几个节点：

连线结果如图：

可以填入相应的费用和容量，可以类比运筹学中的最小费用流

至于其他概念在此不做赘述，比如二部图、完全偶图、星、环、连杆、重边等概念

只填入费用就相当于带权的图，可以求最短路径以及最小生成树

可以指定起点与终点，有向与无向

如果指定容量后还可以求拓扑排序、关键排序、最大流、最大流最小费用流。

ps：有需求请留言，还可以一起交流其他问题

网址：数模 03图论Dijkstra and Floyd matlab 及 软件使用 https://www.yuejiaxmz.com/news/view/249073

相关内容

MATLAB图像处理（包括图像类型转换）
matlab中for循环的简单使用
matlab编程实现美图秀秀,图像配准技术及其MATLAB编程实现源码及自己测试M文件...
基于MATLAB语音识别系统GUI界面
Matlab
Matlab的for循环优化
图书馆信息管理系统用例图
基于MATLAB的智能交通信号灯控制系统的实现
9.回文数
张杰：公交换乘代码优化及其生活应用

随便看看