NOJ-数据结构-实验4_数据结构实验4noj_Phoenix_ZengHao的博客-程序员秘密

技术标签: 算法  NOJ&数据结构&算法设计  图论  数据结构  

原博客: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;
} 
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Phoenix_ZengHao/article/details/109298431

智能推荐

[WTL/ATL]_[初级]_[选择文件或文件夹]_infoworld的博客-程序员秘密

场景之前在文章选择目录对话框里介绍了打开对话框选择文件夹的方法. 但是这两种方式总也有些小问题. 不建议使用了。如果选择文件和文件夹都需要那么麻烦的话, WTL界面库按道理来说应该会集成了这类工具类.说明在WTL库里其实就有两个类来选择文件或文件夹CFileDialog和CFolderDialog, 在MFC里有CFileDialog和CFolderPickerDialog...

MYSQL ERROR CODE 错误编号的意义_csdn_000000000000001的博客-程序员秘密

转载地址:https://blog.csdn.net/liujihaozhy/article/details/51724692MYSQL ERROR CODE 错误编号的意义mysql error code(备忘)转1005:创建表失败1006:创建数据库失败1007:数据库已存在,创建数据库失败1008:数据库不存在,删除数据库失败1009:不能删除数据库文件导...

工具推荐 10款用过都说好的移动界面原型设计工具_OK_boom的博客-程序员秘密

首先,一款优秀的 移动APP界面原型设计工具应该具备:  ①.支持移动端演示(随时随地演示给BOSS,厕所&食堂&电梯…以体现我是那么的敬业——长点工资必备)  ②.组件库(高效复用,谁用谁知道)  ③.可以快速生成全局流程(程序猿看不懂拆解的,给丫的看这个)  ④.在线协作(多个PM狗一起用)  ⑤.手势操作、转场动画、交互特效…(这些都不需要,留给专业的

分享一个 React-Native 气泡球组件_react native 下来气泡_qq_34896500的博客-程序员秘密

github 地址分享一个 React Native 气泡球组件,球在屏幕内按照随机速度移动,球可以由图片和 &amp;lt;View /&amp;gt;生成。特征:球的数量可配置球的大小可配置球的速度可配置样式可配置效果如下:...

RSA加解密VS加签与验签_weixin_34258782的博客-程序员秘密

为什么80%的码农都做不了架构师?&gt;&gt;&gt; ...

2353410-13-4,Ald-CH2-PEG8-azide,CHO-PEG8-azide单分散PEG交联剂,包含叠氮化物基团和醛基团_azide-cho_陕西新研博美的博客-程序员秘密

英文名称:Ald-CH2-PEG8-azide CHO-PEG8-azide化学式:C18H35N3O9分子量:437.5CAS:2353410-13-4纯度:95%储存条件:-20°C溶解性:水、DMSO、DCM、DMF运输:环境温度结构式:Ald-CH2-PEG8-叠氮化物是一种单分散PEG交联剂,包含叠氮化物基团和醛基团。叠氮化物基团通过点击化学实现聚乙二醇化。PEG8间隔增加水介质中的溶解度。醛可通过与肼或肼反应形成水解酰基腙键用于聚乙二醇化。...

随便推点

个人python学习心得第一章_qq_43492681的博客-程序员秘密

在分享python之前先讲一下,自己吧本人是2018入学的大学狗一只,现在就读与网络工程专业,由于个人原因以及作业要求,现在开始写博客在分享python知识之前,我先简单介绍一下自己比较喜欢的python编程软件,相比于IDEA,个人更喜欢anaconda 的jupter notebook。没有啥特殊原因,仅仅是个人喜好,但是据说后期编程会不够用,但是现在自我感觉还阔以!官网上下载anac...

Singleton单例类模式_dfuw13072的博客-程序员秘密

body, table{font-family: 微软雅黑; font-size: 10pt} table{border-collapse: collapse; border: solid gray; border-width: 2px 0 2px 0;} th{border: 1px ...

论一个前端开发者的自我修养_前端开发工程师所应具备的态度_萧文翰的博客-程序员秘密

先做个简单的自我介绍:本人(大名:萧文翰),Android 架构师/技术顾问。从2013年开始从事移动前端开发,主攻 Android 和跨平台开发技术,具有丰富的实战项目经验。国内7项专利共同发明人;图书《Android App Hook and Plug-In Technology》译者(中译英);自2017年底至2019年,担任天津/广州三星通信研究院代码优化工作,期间6次当选 Best Te...

android traceroute 功能实现,在android中实现Traceroute功能_呆呆wang的博客-程序员秘密

这是我第一次提出任何问题,请原谅我的任何错误.我想实现traceroute功能,如Android Play商店中提供的这些应用程序.我知道在windows traceroute中输入CMD时,google.com会显示所有使用的中间IP.现在我试过了.我尝试使用traceroute命令,但android不支持traceroute只有rooted设备支持它.Process process =Runt...

Linux系统InfluxDB数据和日志目录迁移教程_influxdb日志目录_大脑补丁的博客-程序员秘密

本文介绍了InfluxDB v1.8.x版本,数据目录和日志目录的迁移,数据迁移可以使InfluxDB磁盘扩容或者磁盘更换不影响正常使用,也不会丢失数据,日志迁移可以方便我们找到和查看InfluxDB运行日志,日志文件会逐渐增大,也不会撑爆系统盘导致InfluxDB宕机。

CSS——字体、英文间距、大小写及下划线_css 中英文字体大小_ShyuDai的博客-程序员秘密

字体属性font-weight(设置文字的粗细)font-style(设置文字倾斜加粗)font-variant(设置小型大写字母)font-family(设置字体)字体大小(相对单位)&amp;amp;amp;lt;!DOCTYPE html&amp;amp;amp;gt;&amp;amp;amp;lt;html lang=&amp;amp;quot;en&amp;amp;quot;&amp;amp;amp;gt;&amp;amp;amp;lt;head&amp;a

推荐文章

热门文章

相关标签