欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Dijkstra算法 最短路径

程序员文章站 2024-03-16 13:26:04
...

Dijkstra算法思想

 Dikstra算法用于求单源点最短路径问题:给定有向图G=(V、E)和源点v∈V,求从v到G中其余各顶点的最短路径。
 Dikstra算法的基本思想是:将顶点集合V分成两个集合,一类是生长点的集合S,包括源点和已经确定最短路径的顶点;另一类是非生长点的集合V-S,包括所有尚未确定最短路径的顶点,并使用一个待定路径表,存储当前从源点v到每个非生长点的最短路径。初始时,S只包含源点v,对v∈V-S,待定路径表为从源点到的有向边。然后在待定路径表中找到当前最短路径v…vk,将vk加入集合S中,对vi∈V-S,将路径v…vk vi与待定路径表中从源点v到vi的最短路径相比较,取路径长度较小者为当前最短路径。重复上述过程,直到集合V中全部顶点加入到集合S中。

Dijkstra基于的存储结构

  图的存储方式:为了快速的求得任意两个顶点之间边上的权值,图采用邻接矩阵存储。

  辅助数组dist[n]:元素dist[i]表示当前所找到的从源点到终点的最短路长度。初态为:若从v到vi有弧,则dist[i]为弧上的权值;否则置    dist[i]为无穷。若当前求得的终点为vk,则进行迭代:dist[i]={mindist[i ],dist[k]+edge[k]}    0≤i≤n-1
  辅助数组path[n]:元素path[i]是一个字符串,表示当前从源点v到终点vi的最短路径。初态为:若从v到vi有弧,则path[i]=vvi,否则path[i]置为空串。

伪代码:

算法: Dijkstra算法
输入:有向网图G=(V,E),源点v
输出:从v到其他所有顶点的最短路径
1.初始化:S={v};dist[j]=edge[v][j](0≤j≤n)
2.重复下述操作直到S等于V:
  2.1 dist[k]=min{dist[i]}(i∈V-S)
  2.2 S=S+{k}
  2.3 dist[i]=min{dist[i], dist[k] +edge [k][i](i∈V-S)

Dijkstra算法 最短路径

Dijkstra算法实现最短路径例题及实现代码


描述

    给出一个有向图的结构,求某个顶点到另一点的最短路径
输入
    若干行整数,第一行有2个数,分别为顶点数v和弧数a,第二行为起点编号s和终点编号e,接下来有a行,每一行有3个数,分别是该条弧所关联的两个顶点编号和弧的权值
输出
    第一行为一个整数,为最短路径值
    第二行为若干个空格隔开的顶点构成的最短路径序列(用小写字母)
    若无最短路径,直接输出no answer
样例输入

    6 8
    0 3
    0 2 10
    0 4 30
    0 5 100
    1 2 5
    2 3 50
    3 5 10
    4 3 20
    4 5 60

样例输出

    50
    v0 v4 v3

#include<iostream>
#include<string>
using namespace std;
const int maxnum=6;
int Minedge(int a[],int n)
{
	int min=1000;
	int x=0;
	for(int i=1;i<n;i++)
	{
		if(a[i]<min&&a[i]!=0){
		    min=a[i];
			x=i;
			}
		}
	return x;
}
class MGraph
{
	public:
	MGraph(string a[maxnum],int v,int e);
    void Dijkstra(int v1,int v2);
	private:
	string vertex[maxnum];
	int edge[maxnum][maxnum];
	int vertexnum;
	int edgenum;
};
MGraph::MGraph(string a[maxnum],int v,int e)
{
	int i,j,k,l;
	vertexnum=v;
	edgenum=e;
	for(i=0;i<vertexnum;i++)
	    vertex[i]=a[i];
	for(i=0;i<vertexnum;i++)
	    for(j=0;j<vertexnum;j++)
	        edge[i][j]=1000;
	for(k=0;k<edgenum;k++){
		cin>>i>>j>>l;
		edge[i][j]=l;
		}
}
void MGraph::Dijkstra(int v1,int v2)
{
	int i,k;
	int s=0;
	int num,dist[maxnum];
	string path[maxnum];
	for(i=0;i<vertexnum;i++)
	{
		dist[i]=edge[v1][i];
		if(dist[i]!=1000) path[i]=vertex[v1]+" "+vertex[i];
		else path[i]="";
		}
	for(num=1;num<vertexnum;num++)
	{
		k=Minedge(dist,vertexnum);
		for(i=0;i<vertexnum;i++)
		{
			if(dist[i]>dist[k]+edge[k][i]){
				dist[i]=dist[k]+edge[k][i];
				path[i]=path[k]+" "+vertex[i];
				}
		}
		if(k==v2) s=dist[k];
		dist[k]=0;
	}
	if(path[v2]!=""){
		cout<<s<<endl;
	    cout<<path[v2];
	    }
	else cout<<"no answer";
}
int main()
{
	int v,e,m,n;
	cin>>v>>e;
	cin>>m>>n;
	string a[maxnum]={"v0","v1","v2","v3","v4","v5"};
	MGraph mgr(a,v,e);
	mgr.Dijkstra(m,n);
	return 0;
}