数据结构与算法：最短路径

关于最短路径的一些概念

源点：路径起始的第一个顶点。
终点：路径终止的最后一个顶点。
最短路径：对于无权图来说，就是从源点到终点经过的边数最少的路径；对于带权图来说，就是路径上权值之和最少的路径。

常用的最短路径算法有：SPFA算法、Dijkstra算法、Bellman-Ford算法、SPT算法、Floyd算法，将介绍Dijkstra算法和Floyd算法。

Dijkstra算法

迪杰斯特拉算法是一个单源点的最短路径算法，其时间复杂度为O(n^2)。

思路

使用边集数组或者邻接表来存图，并自定义一个辅助数组，分别记录原点到顶点的最短路径和，顶点的来源（该顶点若在最短路径上，则它的上一个顶点称为来源），Visited数组记录是否访问过顶点。
定义一些新的概念：

1. 沉没成本：在源点到终点的过程中，经过的路径上的权值之和。
2. 预期成本：从某一点到终点所经过路径权值之和。
   寻找最短路径的过程就是在寻找中间节点的最小沉没成本和该点的最小预期成本。

完成准备后就可以开始寻找最短路径：

1. 从源点开始寻找与源点相接的点，并更新距离，来源，并标记为以访问。
2. 在距离数组中寻找值最小的顶点，并寻找与其相接的顶点，计算其距离（沉没成本+到相接顶点的与其成本），来源，并标记为已访问。
3. 在距离数组中寻找最小值且未被访问过的节点继续步骤2中查找方法直到所有顶点都被访问。
4. 按照数组中来源从终点开始输出最短路径。

代码实现

定义以下结构:
使用二维矩阵存储图，g为图，nv为顶点数，ne为边数，v为源点。
dist为辅助数组，path为来源数组，Visited为访问数组。

#define INF 625535
#define MaxVertexNum 100;
int g[105][105];
int nv,ne,v;//v是源点
int dist[105],path[105];
int ch[105];

代码

void Dijkstra(Graph& G)
{
	for(int i=0;i<ne;i++)
	{
		dist[i]=g[v][i];
		if(g[v][i]!=INF)
		{
			path[i]=v;
		}
	}
	int minn;//最小的dist 
	int k;//最小dist值是k点 
	for(int i=1;i<nv;i++)
	{
		minn=INF;
		for(int j=0;j<nv;j++)//找最小的dist 
		{
			if(ch[j]==0&&dist[j]<minn)
			{
				minn=dist[j];
				k=j;
			 } 
			
		 } 
		 ch[k]=1;
		 for(int j=0;j<nv;j++)
		 {
		 	if(ch[j]==0&&dist[k]+g[k][j]<dist[j])
		 	{
		 		dist[j]=dist[k]+g[k][j];
		 		path[j]=k;
			 }
		 }
	}
}

Floyd算法

以后再更新（>_<）~

• 本文作者： KongXinQing
• 本文链接： https://13114987559.github.io/2023/09/09/note/数据结构与算法-最短路径/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！