前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最短路径-----迪杰特斯拉算法

最短路径-----迪杰特斯拉算法

作者头像
大忽悠爱学习
发布2021-03-27 17:53:02
7460
发布2021-03-27 17:53:02
举报
文章被收录于专栏:c++与qt学习c++与qt学习

无向图

最短路径:两顶点之间经历的边数最少的路径

网图

最短路径:两顶点之间经历的边上的权值之和最短的路径

在这里插入图片描述
在这里插入图片描述

迪杰特斯拉算法思路:按路径长度递增的次序产生最短路径的算法

图解:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

数据结构

在这里插入图片描述
在这里插入图片描述

伪代码

在这里插入图片描述
在这里插入图片描述

图解:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

伪代码

在这里插入图片描述
在这里插入图片描述

代码解释:

在这里插入图片描述
在这里插入图片描述

邻接矩阵实现

代码语言:javascript
复制
#include<iostream>
using namespace std;
#define Max 10//最大顶点数
#define MANY 65535
class Graph 
{
private:
	int verNum;//顶点个数
	int arcNum;//边的个数
public:
	int ver[Max];//顶点数组
	int arc[Max][Max];//网图的邻接矩阵
public:
	Graph(int v[],int n,int e);
	int getVernum()
	{
		return verNum;
	}
	int getArcnum()
	{
		return arcNum;
	}
          
};
Graph::Graph(int v[],int n,int e)
{
	verNum = n;
	arcNum = e;
	for (int i = 0; i < verNum; i++)
		ver[i] = v[i];
	for (int i = 0; i < verNum; i++)
	{
		for (int j = 0; j < verNum; j++)
		{
			if (i == j)
			{
				arc[i][j] = 0;
			}
			else {
				arc[i][j] = MANY;
			}
		}
	}
	cout << "请输入每条边依附的两个顶点和权值:" << endl;
	int vi=0, vj=0,k=0;
	for (int i = 0; i <arcNum; i++)
	{
		cin >> vi >> vj>>k;
		arc[vi][vj] = k;
	}
}
//查找当前没有放入s中的最小顶点---dist数组  s数组  顶点数
int findMinDist(int dist[], int s[], int verNum)
{ 
	int min = -1;
	for (int i = 0; i < verNum; i++)
	{
		if (s[i] == 0)//当前节点没有被放入S数组
		{
			 min = i;//假设当前节点为最小顶点
			for (int j = 0; j < verNum; j++)
			{
				if (s[j] == 0)
				{
					if (dist[min] > dist[j])//当前j节点对应dist数组中的值更小,即距离更短
					{
						min = j;
					}
				}
			}
		}
	}
	return min;
}
//打印最短路径
void display(int dist[], int path[],int s[], Graph* p,int startV)
{
	int RightPath[Max] = { 0 };
	for (int i = 0; i < p->getVernum(); i++)
	{
		cout << "源点到" << i << "顶点的最短路径:";
		cout << 0;
		int num = 0;//计算最短路径有几个顶点
		RightPath[num++] = i;
		int t = path[i];
		while (t != 0)
		{
			RightPath[num++] = t;
			t = path[t];
		}
		//逆序打印数组,得到最短路径
		for (int j= num - 1; j>= 0; j--)
		{
			cout << RightPath[j];
		}
		cout << endl;
	}
}
//迪杰斯特拉算法:startV----源点,计算的起点
void Dijkstra(Graph* p, int startV)
{
	int dist[Max];//存放最短路径的长度
	int  path[Max];//存放最短路径的下标
	int s[Max] = { 0 };//S数组中存放的是已经计算出最短路径的节点
	//初始化dist数组和path数组
	for (int i = 0; i < p->getVernum(); i++)
	{
		//当s数组中只有一个源点的时候,那么最短路径就是当前源点到U集合中各顶点的距离
		dist[i] = p->arc[startV][i];
	    //s数组一开始只有一个源点,例如源点为0,0一开始只能到U集合的1 2 3顶点,因此到1,2,3顶点的前一个节点下标为0,因为到4,5,6顶点距离为无穷大,所以无法到达4,5,6,path数组中存放的值为-1
		if (dist[i] != MANY)
		{
			//起点为源点
			path[i] = startV;
		}
		else 
		{
			//源点到达不了该顶点,没有起点
			path[i] = -1;

		}
	}
	//源点放入集合s
	s[startV] = 1;
	//计算当前已经放入S集合中的顶点个数,即已经求出最短路径的节点个数
	int num = 1;//一开始只有源点
	int min = 0;//最小顶点的下标
	while (num < p->getVernum())
	{
		//1.查找当前dist数组中s[i]为0的最小顶点
		min = findMinDist(dist, s, p->getVernum());
		//2.将最小顶点放入集合S中
		s[min] = 1;
		//3.新顶点加入后,是否会产生更优解,如果有就更新dist和path数组
		for (int i = 0; i < p->getVernum(); i++)
		{
			if (s[i] == 0 && dist[i] > dist[min] + p->arc[min][i])
			{
				//更新
				dist[i] = dist[min] + p->arc[min][i];//修改到源点到i顶点最短路径
				path[i] = min;//到达当前i顶点最短路径的前一个起点更新
			}
		}
		num++;
	}
	cout << "path数组打印:" << endl;
	for (int i = 0; i < p->getVernum(); i++)
		cout << path[i] << "\t";
	cout << endl;
	cout << "dist数组打印:" << endl;
	for (int i = 0; i < p->getVernum(); i++)
		cout << dist[i] << "\t";
	cout << endl;
	//打印起始点到各顶点的最短路径
	cout << "打印最短路径:" << endl;
	display(dist,path,s, p,startV);
}
//测试----------------------
void test()
{
	int v[7] = { 0,1,2,3,4,5,6 };
	Graph p(v, 7, 12);
	cout << "打印邻接矩阵" << endl;
	for (int i = 0; i < p.getVernum(); i++)
	{
		for (int j = 0; j < p.getVernum(); j++)
		{
			cout << p.arc[i][j]<<"\t";
		}
		cout << endl;
	}
	Dijkstra(&p, 0);

}
int main()
{
	test();
	system("pause");
	return 0;
}
在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-03-25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 无向图
  • 网图
  • 迪杰特斯拉算法思路:按路径长度递增的次序产生最短路径的算法
  • 数据结构
  • 伪代码
  • 图解:
  • 伪代码
  • 邻接矩阵实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档