热门标签
热门文章
- 1【java-数据结构12-双向链表1】
- 2租房数据分析可视化系统 爬虫 Flask框架 大数据（源码）✅
- 3【c++提高1】数据结构之线段树详解_c++线段树
- 4三栏布局与两栏布局_bootstrap实现网格布局中号窗口显示三栏布局,小号窗口实现二栏布局
- 5RabbitMQ学习笔记：4369、5672、15672、25672默认端口号修改_端口 5672 15672 25672
- 6【Hadoop技术篇】hadoop的使用_hadoop怎么用
- 7什么是关键信息基础设施及其安全保护条例_已认定的关键信息基础设施
- 8“AttributeError: module ‘numpy‘ has no attribute ‘float‘”的成功解决方法_module 'numpy' has no attribute 'float
- 9前端HTML——meta标签应用和图片样式的拓展_html网站meta图片
- 10git安装配置教程(小白保姆教程2024最新版)
当前位置: article > 正文
数据结构——详解最短路径之Dijkstra（迪杰斯特拉）算法和Floyd（弗洛伊德）算法及代码实现_迪杰斯特拉算法和弗洛伊德算法代码
作者：小蓝xlanll | 2024-05-17 20:11:50
赞
踩
迪杰斯特拉算法和弗洛伊德算法代码
1.什么是最短路径？
在非网图中，最短路径是指两顶点之间经历的边数最少的路径。
比如这个图，AE就是最短路径
在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。
而在这个图中，ADCE是最短路径
2.Dijkstra算法
迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。
2.1基本思想:
设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。
我想有的同学肯定读不懂，下面我同样用一个实例来解释Dijkstra算法：
比如我们要求在这个图中，从A点到所有点的最短路径
那么首先，我们将A放入集合S中，从A点开始寻找到每个点的距离，从A->C没有直接路径可以到达，因此距离为无穷，然后我们寻找路径最短的点，很明显从A->B路径为10最短，因此我们将B放入集合S中，这意味着我们已经找到了从A到B的最短路径，接下来我们需要从B点出发寻找最短路径
这时我们发现从B点可以到C点，距离为50，然后我们需要比较从A->B->C的长度和从A->C的长度，如果从A->B->C的长度小于从A->C的，那么我们就替换掉，否则还是维持之前的路径不变，很明显60<无穷，因此我们替换掉之前的A->C无穷，B到D和E没有路径，因此不用比较（在编程时路径为无穷，比较后还是路径不会变化），而A点已经加入集合S当中，不需要比较。
比较完成后我们寻找最短路径，发现A->D路径为30最短，因此我们将D点加入集合S中，下次将从D点开始寻找最短路径
好了，接下来我们要从D点出发了，D点到C和E均有路径，我们比较从A->D->C和A->C的长度，发现A->D->C更近，因此替换掉之前的路径，然后比较A->D->E和A->E的路径，100>90，同样替换掉之前的路径。比较完成后寻找最短路径，下次将从C出发寻找路径，同样将C加入集合S中去
C与E结点相连，距离为10，我们比较A->C->E和A->E的距离，发现50+10<100,因此从A->C->E显然比从A->E要近得多，因此替换掉，由于就剩这一个了，所以不用比较，将E加入集合S中，算法结束，我们便找到了从A出发到每个结点得最短路径！
2.2 Dijkstra算法——伪代码
- 初始化数组dist、path和s；
- while (s中的元素个数<n)
2.1 在dist[n]中求最小值，其下标为k；
2.2 输出dist[j]和path[j]；
2.3 修改数组dist和path；
2.4 将顶点vk添加到数组s中；
2.3 代码实现
同样我们需要先进行图的初始化工作
const int MaxSize=100;
const int MAX=10000;//最大距离
struct Path
{
string route[MaxSize];//一点到所有点的最短路径
int t;//t是route[]数组所用的下标，代表一条路径中的第t个点
};
template<class DataType>
class MGraph
{
public:
MGraph();
~MGraph(){}
void DFSTraverse(int v);
void BFSTraverse(int v);
void Dijkstra(int v);
void Floyd();
void PrintfGraphAL();
int vertexNum,arcNum;//图的顶点数和边数
double dist[MaxSize];//一点到所有点的最短距离
double Dist[MaxSize][MaxSize];//任意两点之间的最短距离
Path path[MaxSize];//一点到所有点的最短路径
DataType vertex[MaxSize];//顶点
private:
int arc[MaxSize][MaxSize];//图的边长
bool DFSvisited[MaxSize];//定义一个DFS遍历过标记
bool BFSvisited[MaxSize];//定义一个BFS遍历过标记
};
template<class DataType>//构造函数
MGraph<DataType>::MGraph()
{
int i,j;
fstream fcin_vertex;
fcin_vertex.open("vertex.txt",ios::in);//打开一个文件用于从文件输入顶点
vertexNum=0,arcNum=0;//令顶点数、边数赋值为0
while(!fcin_vertex.eof())
fcin_vertex>>vertex[vertexNum++];
fcin_vertex.close();
memset(DFSvisited,0,sizeof(DFSvisited));//这个函数用来给DFSvisited数组所有成员赋0
memset(BFSvisited,0,sizeof(BFSvisited));
for(i=0;i<vertexNum;i++)
for(j=0;j<vertexNum;j++)
{
if(i==j)
arc[i][j]=0;//如果是相同顶点，则初始化为0
else
arc[i][j]=MAX;//否则将边长初始化为MAX;
}
fstream fcin_arc;
fcin_arc.open("arc.txt",ios::in);//打开一个文件用于从文件输入边
i=0,j=0;
while(i!=-1)
{
fcin_arc>>i;
if(i==-1)
continue;
else
{
fcin_arc>>j;
if(arc[i][j]==0||arc[i][j]==MAX)//如果这条边等于0或者等于MAX,说明这条边还没被修改过，这时候修改一次，边数+1,
//否则，则说明这条边已经被修改过，再修改边数也不会增加
arcNum++;
fcin_arc>>arc[i][j];
arc[j][i]=arc[i][j];//由于是无向图，i到j的距离等于j到i的距离
}
}
fcin_arc.close();
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
然后是Dijkstra算法：
/*迪杰斯特拉算法
1.初始化path数组，dist数组，集合S，把起点v加入path数组，并把所有的从起点v一步能够到达的点加入path数组，把起点的遍历标记S置1
2.执行n-1步循环
2.1在dist数组中找到最小值dist[j]，这个值即为v到j的最小距离，把这个dist值以及对应的path路径输出
2.2以2.1中path的终点k为新的起点，遍历所有的点，找到所有从新的起点k出发到达j（dist[k]+arc[k][j]）
比原来的起点出发到达j（dist[j]）的距离更短的点j，并把dist值修改为dist[k]+arc[k][j]，将path[k]赋给path[j],并将新的点j放入path[j]中
*/
template<class DataType>//迪杰斯特拉算法（求一个点到所有点的最短路径算法）这里设那“一个点”为v点
void MGraph<DataType>::Dijkstra(int v)
{
int i,j,num,b;
bool S[MaxSize];//这是一个点是否被加入到集合S中的标记
for(i=0;i<vertexNum;i++)//初始化dist[]、S[]、path[]数组
{
dist[i]=arc[v][i];//将要寻找的点到所有点的距离初始化，即按照邻接矩阵赋值
S[i]=0;//将所有点是否被加入到集合S中的标记置0，即尚未加入
path[i].t=0;//t是route[]数组所用的下标，代表一条路径中的第t个点，初始化为0
path[i].route[path[i].t]=vertex[v];//将要寻找的点到所有点的路径path[]初始化，即只有起点本身
if(dist[i]!=MAX)//如果将要寻找的点到任意一点i的距离不等于MAX，即起点到点i存在边
path[i].route[++path[i].t]=vertex[i];//就把点i加入路径path[i]中
}
S[v]=1;//开始遍历，将起点的遍历标记置1
for(num=1;num<vertexNum;num++)//循环vertexNum-1次，即有n个点，就得寻找n-1次，每次找出一个点
{
//下面的这个循环将会寻找出从当前起点出发，到达所有点的最小距离
double min=MAX;//记当前起点出发到所有点的距离为min{len<v,j>}，初始化min{len<V,j>}=MAX
int k=v;//k为min{len<v,j>}最小的点，初始为起点
for(j=0;j<vertexNum;j++)//在dist[]中寻找最小值
if(S[j]==0&&dist[j]!=0&&dist[j]<=min)//如果有一个点j，满足:没有被加入到S[]，并且到点v的距离不是0（不是v点本身），并且距离小于当前最小值
{
k=j;//保存j点的下标到k中
min=dist[j];//令当前的最小值为dist[k]
}
S[k]=1;//把k点放入S[]
for(j=0;j<vertexNum;j++)//现在的起点为k，再次遍历所有点寻找有没有点j 满足:从新的起点k出发（dist[k]+arc[k][j]）
//到达j比原来的起点出发到达j的距离更短
if(S[j]==0&&arc[k][j]<MAX)//如果点j没有加入S[]并且k点到j点有边（距离不为MAX）
{
if(dist[j]>dist[k]+arc[k][j])//这步意图在 比较从之前的起点出发到达j（dist[j]）和 从新的起点k出发到达j（dist[k]+arc[k][j]）
//哪种方式距离更短，取更短的那种
{
dist[j]=dist[k]+arc[k][j];//如果从k更短，就把更短的距离赋给dist[j]
for(b=0;b<=path[k].t;b++)//把path[k].route复制给path[j].route
path[j].route[b]=path[k].route[b];
path[j].t=path[k].t;
path[j].route[++path[j].t]=vertex[j];//将点j加入path[j].route
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
3.Floyd算法
3.1 基本思想
对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。
比如下面这个有向网图，我们来寻找任意两点间得最短距离：
首先是初始化，标记出开始是相邻两点间得路径和长度
从a开始第一次迭代，我们发现从c->b的长度和从c->a->b要大，因此把路径替换为cab，长度为7（之前为无穷），而从b->c的距离为2，比从b->a->c要短的多，因此不换
同理，从b开始第二次迭代，将a->c替换为a->b->c
从c开始第三次迭代，将b->a替换为b->c->a
这样我们便找到了任意两点间的最短路径和长度！
3.2 代码实现
template<class DataType>//Floyd算法（求任意一点到任意一点的最短路径算法）
void MGraph<DataType>::Floyd()
{
int i,j,k;
for(i=0;i<vertexNum;i++)
for(j=0;j<vertexNum;j++)
Dist[i][j]=arc[i][j];//将任意两点之间的距离初始化，即按照邻接矩阵赋值
//下面相当于运用了vertexNum次Dijkstra算法
for(k=0;k<vertexNum;k++)
//下面的双重循环将用来找出所有 满足:i经过k到达j的距离<i按照之前路径到达j的距离 这一条件的点
for(i=0;i<vertexNum;i++)
for(j=0;j<vertexNum;j++)
if(Dist[i][k]+Dist[k][j]<Dist[i][j])//如果i经过k到达j的距离<i直接到达j的距离
Dist[i][j]=Dist[i][k]+Dist[k][j];//把i到j的距离改为如果i经过k到达j的距离
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
4. 完整代码附录如下：(需要读取两个txt文件，分别存放点信息和边信息)
#include<iostream>
using namespace std;
#include<conio.h>//getch()函数头文件
#include<string>//新版vc的getch()函数头文件
#include<stdlib.h>//调节颜色头文件
#include<fstream>
const int MaxSize=100;
const int MAX=10000;//最大距离
struct Path
{
string route[MaxSize];//一点到所有点的最短路径
int t;//t是route[]数组所用的下标，代表一条路径中的第t个点
};
template<class DataType>
class MGraph
{
public:
MGraph();
~MGraph(){}
void DFSTraverse(int v);
void BFSTraverse(int v);
void Dijkstra(int v);
void Floyd();
void PrintfGraphAL();
int vertexNum,arcNum;//图的顶点数和边数
double dist[MaxSize];//一点到所有点的最短距离
double Dist[MaxSize][MaxSize];//任意两点之间的最短距离
Path path[MaxSize];//一点到所有点的最短路径
DataType vertex[MaxSize];//顶点
private:
int arc[MaxSize][MaxSize];//图的边长
bool DFSvisited[MaxSize];//定义一个DFS遍历过标记
bool BFSvisited[MaxSize];//定义一个BFS遍历过标记
};
template<class DataType>//构造函数
MGraph<DataType>::MGraph()
{
int i,j;
fstream fcin_vertex;
fcin_vertex.open("vertex.txt",ios::in);//打开一个文件用于从文件输入顶点
vertexNum=0,arcNum=0;//令顶点数、边数赋值为0
while(!fcin_vertex.eof())
fcin_vertex>>vertex[vertexNum++];
fcin_vertex.close();
memset(DFSvisited,0,sizeof(DFSvisited));//这个函数用来给DFSvisited数组所有成员赋0
memset(BFSvisited,0,sizeof(BFSvisited));
for(i=0;i<vertexNum;i++)
for(j=0;j<vertexNum;j++)
{
if(i==j)
arc[i][j]=0;//如果是相同顶点，则初始化为0
else
arc[i][j]=MAX;//否则将边长初始化为MAX;
}
fstream fcin_arc;
fcin_arc.open("arc.txt",ios::in);//打开一个文件用于从文件输入边
i=0,j=0;
while(i!=-1)
{
fcin_arc>>i;
if(i==-1)
continue;
else
{
fcin_arc>>j;
if(arc[i][j]==0||arc[i][j]==MAX)//如果这条边等于0或者等于MAX,说明这条边还没被修改过，这时候修改一次，边数+1,
//否则，则说明这条边已经被修改过，再修改边数也不会增加
arcNum++;
fcin_arc>>arc[i][j];
arc[j][i]=arc[i][j];//由于是无向图，i到j的距离等于j到i的距离
}
}
fcin_arc.close();
}
template<class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{
int j;
cout<<vertex[v]<<" ";//遍历到该点，即输出
DFSvisited[v]=1;//然后将该点的遍历标记置1
for(j=0;j<vertexNum;j++)
if(arc[v][j]!=0&&arc[v][j]!=MAX&&DFSvisited[j]==0)//如果边不等于0并且不等于MAX并且该点没有遍历过,就深度优先遍历
DFSTraverse(j);
}
template<class DataType>//广度优先遍历
void MGraph<DataType>::BFSTraverse(int v)
{
int Q[MaxSize];
int front=-1,rear=-1,j;
cout<<vertex[v]<<" ";//先输出开始广度遍历的结点
BFSvisited[v]=1;//并把刚才输出的结点标记为1
Q[++rear]=v;//将该结点入队
while(front!=rear)//如果队非空
{
v=Q[++front];//把队头结点出队，并将出队的结点的数组下标赋给v
for(j=0;j<vertexNum;j++)//for循环寻找下一个满足 边不等于0并且不等于MAX并且该点没有遍历过 的结点
if(arc[v][j]!=0&&arc[v][j]!=MAX&&BFSvisited[j]==0)//如果边不等于0并且不等于MAX并且该点没有遍历过
{
cout<<vertex[j]<<" ";//输出找到的结点
BFSvisited[j]=1;//标记置1
Q[++rear]=j;//结点入队
}
}
}
/*迪杰斯特拉算法
1.初始化path数组，dist数组，集合S，把起点v加入path数组，并把所有的从起点v一步能够到达的点加入path数组，把起点的遍历标记S置1
2.执行n-1步循环
2.1在dist数组中找到最小值dist[j]，这个值即为v到j的最小距离，把这个dist值以及对应的path路径输出
2.2以2.1中path的终点k为新的起点，遍历所有的点，找到所有从新的起点k出发到达j（dist[k]+arc[k][j]）
比原来的起点出发到达j（dist[j]）的距离更短的点j，并把dist值修改为dist[k]+arc[k][j]，将path[k]赋给path[j],并将新的点j放入path[j]中
*/
template<class DataType>//迪杰斯特拉算法（求一个点到所有点的最短路径算法）这里设那“一个点”为v点
void MGraph<DataType>::Dijkstra(int v)
{
int i,j,num,b;
bool S[MaxSize];//这是一个点是否被加入到集合S中的标记
for(i=0;i<vertexNum;i++)//初始化dist[]、S[]、path[]数组
{
dist[i]=arc[v][i];//将要寻找的点到所有点的距离初始化，即按照邻接矩阵赋值
S[i]=0;//将所有点是否被加入到集合S中的标记置0，即尚未加入
path[i].t=0;//t是route[]数组所用的下标，代表一条路径中的第t个点，初始化为0
path[i].route[path[i].t]=vertex[v];//将要寻找的点到所有点的路径path[]初始化，即只有起点本身
if(dist[i]!=MAX)//如果将要寻找的点到任意一点i的距离不等于MAX，即起点到点i存在边
path[i].route[++path[i].t]=vertex[i];//就把点i加入路径path[i]中
}
S[v]=1;//开始遍历，将起点的遍历标记置1
for(num=1;num<vertexNum;num++)//循环vertexNum-1次，即有n个点，就得寻找n-1次，每次找出一个点
{
//下面的这个循环将会寻找出从当前起点出发，到达所有点的最小距离
double min=MAX;//记当前起点出发到所有点的距离为min{len<v,j>}，初始化min{len<V,j>}=MAX
int k=v;//k为min{len<v,j>}最小的点，初始为起点
for(j=0;j<vertexNum;j++)//在dist[]中寻找最小值
if(S[j]==0&&dist[j]!=0&&dist[j]<=min)//如果有一个点j，满足:没有被加入到S[]，并且到点v的距离不是0（不是v点本身），并且距离小于当前最小值
{
k=j;//保存j点的下标到k中
min=dist[j];//令当前的最小值为dist[k]
}
S[k]=1;//把k点放入S[]
/*if(dist[k]<MAX)
{
cout<<v<<vertex[v]<<"到"<<k<<vertex[k]<<"的最短路径为:"<<endl;
for(j=0;j<path[k].t;j++)
cout<<path[k].route[j]<<"->";
cout<<path[k].route[j];
cout<<"\t最小距离为"<<dist[k]<<endl;//输出起点v到点k的最短路径和最小距离
}
else
cout<<vertex[v]<<"不能到点"<<vertex[k]<<endl;*/
for(j=0;j<vertexNum;j++)//现在的起点为k，再次遍历所有点寻找有没有点j 满足:从新的起点k出发（dist[k]+arc[k][j]）
//到达j比原来的起点出发到达j的距离更短
if(S[j]==0&&arc[k][j]<MAX)//如果点j没有加入S[]并且k点到j点有边（距离不为MAX）
{
if(dist[j]>dist[k]+arc[k][j])//这步意图在 比较从之前的起点出发到达j（dist[j]）和 从新的起点k出发到达j（dist[k]+arc[k][j]）
//哪种方式距离更短，取更短的那种
{
dist[j]=dist[k]+arc[k][j];//如果从k更短，就把更短的距离赋给dist[j]
for(b=0;b<=path[k].t;b++)//把path[k].route复制给path[j].route
path[j].route[b]=path[k].route[b];
path[j].t=path[k].t;
path[j].route[++path[j].t]=vertex[j];//将点j加入path[j].route
}
}
}
}
template<class DataType>//Floyd算法（求任意一点到任意一点的最短路径算法）
void MGraph<DataType>::Floyd()
{
int i,j,k;
for(i=0;i<vertexNum;i++)
for(j=0;j<vertexNum;j++)
Dist[i][j]=arc[i][j];//将任意两点之间的距离初始化，即按照邻接矩阵赋值
//下面相当于运用了vertexNum次Dijkstra算法
for(k=0;k<vertexNum;k++)
//下面的双重循环将用来找出所有 满足:i经过k到达j的距离<i按照之前路径到达j的距离 这一条件的点
for(i=0;i<vertexNum;i++)
for(j=0;j<vertexNum;j++)
if(Dist[i][k]+Dist[k][j]<Dist[i][j])//如果i经过k到达j的距离<i直接到达j的距离
Dist[i][j]=Dist[i][k]+Dist[k][j];//把i到j的距离改为如果i经过k到达j的距离
}
int main()
{
MGraph<string> graph;//构造图
char N;
int i,j;
system("color 0A");
while(true)
{
cout<<"请输入需要的功能N："<<endl;
cout<<"0.退出\n";
cout<<"1.统计图中边数\n";
cout<<"2.深度优先遍历\n";
cout<<"3.广度优先遍历\n";
cout<<"4.求一地点到所有地点的距离\n";
cout<<"5.求一地点到另一地点的距离\n";
cin>>N;
if(N=='0')break;
switch(N)
{
case '1':
cout<<"图的边数为:"<<graph.arcNum<<endl;
cout<<"--请按任意键继续--\n";
_getch();
system("CLS");
break;
case '2':
cout<<"图的深度优先遍历结果为:";
graph.DFSTraverse(0);
cout<<endl;
cout<<"--请按任意键继续--\n";
_getch();
system("CLS");
break;
case '3':
cout<<"图的广度优先遍历结果为:";
graph.BFSTraverse(0);
cout<<endl;
cout<<"--请按任意键继续--\n";
_getch();
system("CLS");
break;
case '4':
int v;
cout<<"请输入求哪个(0~15)点到其他点的最小距离:";
cin>>v;
graph.Dijkstra(v);
for(i=0;i<graph.vertexNum;i++)
{
if(i!=v)
{
cout<<v<<graph.vertex[v]<<"到"<<i<<graph.vertex[i]<<"的最短路径为:"<<endl;
for(j=0;j<graph.path[i].t;j++)
cout<<graph.path[i].route[j]<<"->";
cout<<graph.path[i].route[j];
cout<<"\t最小距离为"<<graph.dist[i]<<endl;//输出起点v到点k的最短路径和最小距离
}
}
cout<<"--请按任意键继续--\n";
_getch();
system("CLS");
break;
case '5':
int i1,i2;
graph.Floyd();
cout<<"请输入第一个点(0~15):";
cin>>i1;
cout<<"请输入第二个点(0~15):";
cin>>i2;
graph.Dijkstra(i1);
cout<<i1<<graph.vertex[i1]<<"到"<<i2<<graph.vertex[i2]<<"的最短路径为:"<<endl;
for(j=0;j<graph.path[i2].t;j++)
cout<<graph.path[i2].route[j]<<"->";
cout<<graph.path[i2].route[j];
cout<<"最小距离是:"<<graph.Dist[i1][i2]<<endl;
cout<<"--请按任意键继续--\n";
_getch();
system("CLS");
break;
default:
cout<<"输入错误，请重新输入!\n";
cout<<"--请按任意键继续--\n";
_getch();
system("CLS");
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
点信息txt文件如下，命名为vertex
西街 公寓楼 鸿远楼 修远楼 明远楼 逸夫图书馆 行政楼 南门 树慧园 天行健 澡堂 北门 操场 仙女楼
校医院 东门
- 1
- 2
边信息txt文件如下，命名为arc
0 1 50
0 2 80
1 2 100
1 3 200
2 4 200
3 4 100
3 5 150
4 5 70
4 6 70
5 6 100
5 8 300
6 7 50
8 9 100
8 10 70
8 13 50
9 10 70
10 12 50
10 13 150
12 11 150
12 13 50
13 14 300
13 15 100
-1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
点和边信息大家也可自行定义
5.运行结果如下:
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/585069
推荐阅读
相关标签
