使用邻接矩阵实现有向图最短路径Dijkstra算法 题目编号:1136

这篇具有很好参考价值的文章主要介绍了使用邻接矩阵实现有向图最短路径Dijkstra算法 题目编号:1136。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

用邻接矩阵存储有向图,实现最短路径Dijkstra算法,图中边的权值为整型,顶点个数少于10个。

部分代码提示:
#include
#include
using namespace std;

const int MaxSize = 10;
const int INF = 32767;

class MGraph
{
public:
MGraph(char a[], int n, int e);

void Dijkstra();

private:
char vertex[MaxSize];
int arc[MaxSize][MaxSize];
int vertexNum, arcNum;
};

MGraph::MGraph(char a[], int n, int e)
{
//write your code.

}

int Min(int dist[], int vertexNum)
{
//write your code.

}
void MGraph::Dijkstra()
{
//write your code.

}

int main()
{
int n = 0;
int e = 0;
cin >> n >> e;
char p[MaxSize];
int i = 0;

for (i=0; i<n; i++)
{
	cin >> p[i];
}

MGraph MG(p, n, e);

MG.Dijkstra();

return 0;

}

输入描述

首先输入图中顶点个数和边的条数;
再输入顶点的信息(字符型);
再输入各边及其权值。

输出描述

依次输出从编号为0的顶点开始的从小到大的所有最短路径,每条路径及其长度占一行。

输入样例

5 7
A B C D E
0 1 6
0 2 2
0 3 1
1 2 4
1 3 3
2 4 6
3 4 7

输出样例

AD 1
AC 2
AB 6
ADE 8
内存阀值:50240K 耗时阀值:5000MS文章来源地址https://www.toymoban.com/news/detail-428824.html

代码

#include <iostream>
#include <string>
using namespace std;
 
const int MaxSize = 10;
const int INF = 32767;
 
class MGraph
{
public:
	MGraph(string a[], int n, int e);
 
	void Dijkstra();
 
private:
	string vertex[MaxSize];
	int arc[MaxSize][MaxSize];
	int vertexNum, arcNum;
};
 
MGraph::MGraph(string a[], int n, int e)
{
	//1、赋值
	vertexNum = n;
	arcNum = e;
	//2、顶点表
	for (int i = 0; i < vertexNum; i++)
		vertex[i] = a[i];
	//3、边表初始化
	for (int i = 0; i < vertexNum; i++)
		for (int j = 0; j < vertexNum; j++)
			arc[i][j] = INF;
	//4、边表赋值
	int i = 0, j = 0, w = 0;
	for (int k = 0; k < arcNum; k++)
	{
		cin >> i >> j >> w;
		arc[i][j] = w;
		//arc[j][i] = w;//有方向的不用反复设置相同!!!!掉坑了我淦!
	}
}
 
int Min(int dist[], int vertexNum)
{
	int min = INF;
	
	int pos = 0;
 
	for (int i = 0; i < vertexNum; i++)
	{
		if (dist[i] < min && dist[i] != 0)//!=0?:存入的顶点不需要遍历
		{
			min = dist[i];
 
			pos = i;
		}
	}
	return pos;
}
 
void MGraph::Dijkstra()
{
	int v = 0;
	int i, k, num, dist[MaxSize];//权值表
	string path[MaxSize];//路径表
	for (i = 0; i < vertexNum; i++)
	{
		dist[i] = arc[v][i];//v-表示当前顶点,i-表示这个顶点与其他顶点的边的权值(希望屏幕前的你能理解)
 
		if (dist[i] != INF)//如果连通
			path[i] = vertex[v] + vertex[i];
		else
			path[i] = "";
	}
 
	dist[0] = 0;
	
	for (num = 1; num < vertexNum; num++)//不知道为什么=1?顶点表已经在集合中了,所以不用遍历
	{
		k = Min(dist, vertexNum);
		
		cout << path[k] <<' ' << dist[k];
 
		for (i = 0; i < vertexNum; i++)//更新最小权值表
		{
			if (dist[i] > dist[k] + arc[k][i])
			{
				dist[i] = dist[k] + arc[k][i];
 
				path[i] = path[k] + vertex[i];
			}
		}
		dist[k] = 0;//将k加入集合,为什么是0?因为0比其他路径权值和都要小所以无法改变
	}
}
 
int main()
{
	int n = 0;
	int e = 0;
	cin >> n >> e;
	string p[MaxSize];
	int i = 0;
 
	for (i = 0; i < n; i++)
	{
		cin >> p[i];
	}
 
	MGraph MG(p, n, e);
 
	MG.Dijkstra();
 
	return 0;
}

到了这里,关于使用邻接矩阵实现有向图最短路径Dijkstra算法 题目编号:1136的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点a到顶点b的路径

    试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点a到顶点b的路径,注意a!=b(必须严格按照样例进行输入输出,先输入图的顶点数和弧数,并依次输入弧的相关信息,最后输入要判断的两个顶点的信息) 样例如下: 输入: 5 4 2 4 2 1

    2024年02月15日
    浏览(40)
  • 使用颜色检测有向图中的循环

    给定一个有向图,检查该图是否包含循环。如果给定的图形至少包含一个循环,您的函数应返回 true,否则返回 false。 例子:   输入:  n = 4, e = 6  0 - 1, 0 - 2, 1 - 2, 2 - 0, 2 - 3, 3 - 3  输出: 是  解释:    

    2024年02月03日
    浏览(44)
  • 有向图的拓扑排序

    拓扑排序 。任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到

    2024年02月09日
    浏览(48)
  • 用go语言实现一个构建有向图的函数,同时图结构的点和边上都支持添加属性

    当然可以。下面是一个简单的用Go语言实现的有向图构建函数的示例。这个图结构使用map来存储,每个节点都由一个唯一的标识符(id)表示,并且节点和边都可以附加属性。 go 这个示例代码创建了一个有向图,并添加了两个节点(A和B)和一个从A到B的边。每个节点和边都有

    2024年01月20日
    浏览(33)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(39)
  • 公开游戏、基于有向图的游戏

    目录 〇,背景 一,公开游戏、策梅洛定理 1,公开游戏 2,策梅洛定理 3,非有向图游戏的公开游戏 力扣 486. 预测赢家(区间DP) 力扣 877. 石子游戏(退化贪心) 力扣 1140. 石子游戏 II(二维DP) 力扣 1406. 石子游戏 III(数列DP) 力扣 1563. 石子游戏 V(区间DP)  力扣 1686.

    2024年02月09日
    浏览(44)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(84)
  • 真题详解(有向图)-软件设计(六十二)

    真题详解(极限编程)-软件设计(六十一) https://blog.csdn.net/ke1ying/article/details/130435971 CMM指软件成熟度模型,一般1级成熟度最低,5级成熟度最高,采用更高级的CMM模型可以提高软件质量。 初始:杂乱无章。 可重复级:建立基本的项目管理过程和跟踪费用项。 已定义(确定)

    2024年02月01日
    浏览(63)
  • 2023-04-09 有向图及相关算法

    有向图的的应用场景 社交网络中的关注 互联网连接 程序模块的引用 任务调度 学习计划 食物链 论文引用 无向图是特殊的有向图,即每条边都是双向的 改进Graph和WeightedGraph类使之支持有向图 Graph类的改动 WeightedGraph类的改动 有些问题,在有向图中不存在,或者我们通常不考

    2024年02月05日
    浏览(46)
  • 2023-8-29 有向图的拓扑排序

    题目链接:有向图的拓扑排序

    2024年02月11日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包