我是靠谱客的博主 落寞书本，最近开发中收集的这篇文章主要介绍NOJ-数据结构-实验4实验4.1：求赋权图中一个结点到所有结点的最短路径的长度实验4.2：用迪杰斯特拉算法求赋权图中的最短路径实验4.3：用弗洛伊德算法求赋权图的两点间的最短路径的长度实验4.4：用弗洛伊德算法求赋权图中任意两点间的最短路径，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
原博客：http://phoenix-zh.cn/2020/06/21/NOJ/
实验4.1：求赋权图中一个结点到所有结点的最短路径的长度
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
//---------------------------------------------邻接矩阵-------------------------------------------------------------------------------//
struct AdjMatrix
{
int V,E;
char Vexs[maxn];
int Edge[maxn][maxn];
};
int vis[maxn],path[maxn],dist[maxn];
//----------创建、初始化图----引用图G，节点数V，边数E---------------//
void CreateAdjMatrix(AdjMatrix &G,int V,int E)
{
G.E=E;G.V=V;
for(int i=1;i<=G.V;i++)
{
for(int j=1;j<=G.V;j++)
{
if(i==j)continue;
G.Edge[i][j]=10000;
}
}
for(int i=1;i<=V;i++)
{
for(int j=1;j<=V;j++)
{
int w;
cin>>w;//输入权值
G.Edge[i][j]=w;
}
}
}
void Dijkstra(AdjMatrix &G)
{
int s=1;
for(int i=1;i<=G.V;i++)
{
dist[i]=10000;//初始化起点1到别的所有点的距离，设置为10000
}
for(int i=1;i<=G.V;i++)
{
dist[i]=G.Edge[s][i];//初步更新起点1到别的结点的距离
if(G.Edge[s][i]<10000)
{
path[i]=s;//如果起点s与结点i之间存在边，则i的上一个结点就是s
}
else
{
path[i]=-1;//如果起点s与结点i之间不存在边，则i的上一个结点就是-1，即不存在
}
}
vis[s]=1;path[s]=-1;//起点s标记掉，并且它的上一个结点为-1，即不存在
for(int i=1;i<=G.V-1;i++)
{
int minn=10000,now=0;//每一次要选择一个最优的点作为松弛的中间结点，minn为权值的中间结点到起点s的最近点
for(int j=1;j<=G.V;j++)
{
if(!vis[j]&&dist[j]<minn)
{
now=j;
minn=dist[j];//如果j未被标记，并且离起点s更近，则更新minn和now
}
}
vis[now]=1;//now就是 松弛的中间结点，标记掉它
for(int j=1;j<=G.V;j++)
{
if(!vis[j]&&dist[now]+G.Edge[now][j]<dist[j])
{
dist[j]=dist[now]+G.Edge[now][j];
path[j]=now;//松弛所有未被标记的结点，并且被松弛过的点，它的上一个点就是now
}
}
}
}
//---------------------------------------------邻接矩阵-------------------------------------------------------------------------------//
int n;AdjMatrix G;
int main()
{
cin>>n;//邻接矩阵的图的结点数
CreateAdjMatrix(G,n,n);//建图，n*n的方针
Dijkstra(G);//Dijkstra跑最短路
for(int i=1;i<=G.V;i++)
{
cout<<dist[i]<<endl;//输出结点0-(i-1)的最短路
}
return 0;
}
实验4.2：用迪杰斯特拉算法求赋权图中的最短路径
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
//---------------------------------------------邻接矩阵-------------------------------------------------------------------------------//
struct AdjMatrix
{
int V,E;
char Vexs[maxn];
int Edge[maxn][maxn];
};
int vis[maxn],path[maxn],dist[maxn];
//----------创建、初始化图----引用图G，节点数V，边数E---------------//
void CreateAdjMatrix(AdjMatrix &G,int V,int E)
{
G.E=E;G.V=V;
for(int i=1;i<=G.V;i++)
{
for(int j=1;j<=G.V;j++)
{
if(i==j)continue;
G.Edge[i][j]=10000;
}
}
for(int i=1;i<=V;i++)
{
for(int j=1;j<=V;j++)
{
int w;
cin>>w;//输入权值
G.Edge[i][j]=w;
}
}
}
void Dijkstra(AdjMatrix &G,int s)
{
for(int i=1;i<=G.V;i++)
{
dist[i]=10000;//初始化起点1到别的所有点的距离，设置为10000
}
for(int i=1;i<=G.V;i++)
{
dist[i]=G.Edge[s][i];//初步更新起点1到别的结点的距离
if(G.Edge[s][i]<10000)
{
path[i]=s;//如果起点s与结点i之间存在边，则i的上一个结点就是s
}
else
{
path[i]=-1;//如果起点s与结点i之间不存在边，则i的上一个结点就是-1，即不存在
}
}
vis[s]=1;path[s]=-1;//起点s标记掉，并且它的上一个结点为-1，即不存在
for(int i=1;i<=G.V-1;i++)
{
int minn=10000,now=0;//每一次要选择一个最优的点作为松弛的中间结点，minn为权值的中间结点到起点s的最近点
for(int j=1;j<=G.V;j++)
{
if(!vis[j]&&dist[j]<minn)
{
now=j;
minn=dist[j];//如果j未被标记，并且离起点s更近，则更新minn和now
}
}
vis[now]=1;//now就是 松弛的中间结点，标记掉它
for(int j=1;j<=G.V;j++)
{
if(!vis[j]&&dist[now]+G.Edge[now][j]<dist[j])
{
dist[j]=dist[now]+G.Edge[now][j];
path[j]=now;//松弛所有未被标记的结点，并且被松弛过的点，它的上一个点就是now
}
}
}
}
//---------------------------------------------邻接矩阵-------------------------------------------------------------------------------//
int n;AdjMatrix G;int road[maxn];
int main()
{
cin>>n;//邻接矩阵的图的结点数
CreateAdjMatrix(G,n,n);//建图，n*n的方针
int s,t;//接下来要求解的最短路径的起点s，终点v
cin>>s>>t;//输入 起点s，终点v
s++;t++; //由于起始点为1
Dijkstra(G,s);//Dijkstra跑最短路
int opt=0;//road数组中的数量
while(t!=-1)//停止信号是t==-1
{
road[++opt]=t-1;//road用于记录路径中的结点编号，注意输出的要求0为起始点，所以这里要-1
t=path[t];//终点回溯至上一个点
}
while(opt)//倒序输出road
{
cout<<road[opt]<<endl;//输出路径结点号
opt--;
}
return 0;
}
实验4.3：用弗洛伊德算法求赋权图的两点间的最短路径的长度
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
//---------------------------------------------邻接矩阵-------------------------------------------------------------------------------//
struct AdjMatrix
{
int V,E;
char Vexs[maxn];
int Edge[maxn][maxn];
};
//----------创建、初始化图----引用图G，节点数V，边数E---------------//
void CreateAdjMatrix(AdjMatrix &G,int V,int E)
{
G.E=E;G.V=V;
for(int i=1;i<=G.V;i++)
{
for(int j=1;j<=G.V;j++)
{
if(i==j)continue;
G.Edge[i][j]=10000;
}
}
for(int i=1;i<=V;i++)
{
for(int j=1;j<=V;j++)
{
int w;
cin>>w;//输入权值
G.Edge[i][j]=w;
}
}
}
void Floyd(AdjMatrix &G)
{
for(int k=1;k<=G.V;k++)//枚举中间松弛点
{
for(int i=1;i<=G.V;i++)//枚举起点
{
for(int j=1;j<=G.V;j++)//枚举终点
{
G.Edge[i][j]=min(G.Edge[i][j],G.Edge[i][k]+G.Edge[k][j]);//权值松弛
}
}
}
}
//---------------------------------------------邻接矩阵-------------------------------------------------------------------------------//
int n,m;AdjMatrix G;
int main()
{
cin>>n;//邻接矩阵的图的结点数
CreateAdjMatrix(G,n,n);//建图，n*n的方针
Floyd(G);//Floyd跑最短路
cin>>m;//测试最短路的组数
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;//输入起点和终点
u++;v++;//注意这里0对应的是1（计数从1开始）
cout<<G.Edge[u][v]<<endl;//输出u-->v的最短路的权值
}
return 0;
}
实验4.4：用弗洛伊德算法求赋权图中任意两点间的最短路径
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
//---------------------------------------------邻接矩阵-------------------------------------------------------------------------------//
struct AdjMatrix
{
int V,E;
char Vexs[maxn];
int Edge[maxn][maxn];
};
int path[maxn][maxn];
//----------创建、初始化图----引用图G，节点数V，边数E---------------//
void CreateAdjMatrix(AdjMatrix &G,int V,int E)
{
G.E=E;G.V=V;
for(int i=1;i<=G.V;i++)
{
for(int j=1;j<=G.V;j++)
{
if(i==j)continue;
G.Edge[i][j]=10000;
}
}
for(int i=1;i<=V;i++)
{
for(int j=1;j<=V;j++)
{
int w;
cin>>w;//输入权值
G.Edge[i][j]=w;
}
}
}
void Floyd(AdjMatrix &G)
{
for(int i=1;i<=G.V;i++)
{
for(int j=1;j<=G.V;j++)
{
if(G.Edge[i][j]<10000&&i!=j)//当i j两节点存在路径时
{
path[i][j]=i;//初始化
}
else
{
path[i][j]=-1;//否则记为-1
}
}
}
for(int k=1;k<=G.V;k++)//枚举中间松弛点
{
for(int i=1;i<=G.V;i++)//枚举起点
{
for(int j=1;j<=G.V;j++)//枚举终点
{
if(G.Edge[i][k]+G.Edge[k][j]<G.Edge[i][j])
{
G.Edge[i][j]=G.Edge[i][k]+G.Edge[k][j];//权值松弛
path[i][j]=path[k][j];
}
}
}
}
}
//---------------------------------------------邻接矩阵-------------------------------------------------------------------------------//
int n,m;AdjMatrix G;int road[maxn];
int main()
{
cin>>n;//邻接矩阵的图的结点数
CreateAdjMatrix(G,n,n);//建图，n*n的方针
Floyd(G);//Floyd跑最短路
cin>>m;//测试需要输出最短路径的组数
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;//输入起点和终点
u++;v++;//注意这里0对应的是1（计数从1开始）
int opt=0;//road数组中的数量
road[++opt]=v-1;
while(path[u][v]!=-1)//停止信号是path[u][v]==-1
{
road[++opt]=path[u][v]-1;//road用于记录路径中的结点编号，注意输出的要求0为起始点，所以这里要-1
v=path[u][v];//终点回溯至上一个点
}
while(opt)//倒序输出road
{
cout<<road[opt]<<endl;//输出路径结点号
opt--;
}
}
return 0;
}
最后
以上就是落寞书本为你收集整理的NOJ-数据结构-实验4实验4.1：求赋权图中一个结点到所有结点的最短路径的长度实验4.2：用迪杰斯特拉算法求赋权图中的最短路径实验4.3：用弗洛伊德算法求赋权图的两点间的最短路径的长度实验4.4：用弗洛伊德算法求赋权图中任意两点间的最短路径的全部内容，希望文章能够帮你解决NOJ-数据结构-实验4实验4.1：求赋权图中一个结点到所有结点的最短路径的长度实验4.2：用迪杰斯特拉算法求赋权图中的最短路径实验4.3：用弗洛伊德算法求赋权图的两点间的最短路径的长度实验4.4：用弗洛伊德算法求赋权图中任意两点间的最短路径所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[詹兴致矩阵论习题参考解答]习题1.13](/uploads/reation/bcimg7.png)
![[詹兴致矩阵论习题参考解答]习题3.15](/uploads/reation/bcimg8.png)
发表评论 取消回复