Dijkstra算法 最短路径
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算法实现最短路径例题及实现代码
描述
给出一个有向图的结构,求某个顶点到另一点的最短路径
输入
若干行整数,第一行有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;
}
上一篇: 最短路径 Dijkstra算法
下一篇: Dijkstra最短路径算法