Dijkstra算法
Dijkstra算法
Dijkstra老爷子也是在计算机领域的名人了,在程序设计,编译器,操作系统,图论等方面都经常出现。他的一句最出名的名言就是:“有效的程序员不应该浪费时间用于程序调试,它们应该一开始就不要把故障已经纳入”,Dijkstra算法就是以他命名的常用的最短路径算法
Dijkstra算法的过程是:
第一步,先找到从源点到各个顶点的直达的路径,源点就是起点,简而言之你想求得从A0顶点到A9顶点的最短路径,那么A0就是源点,源点直达的路径就是与其直接相连的顶点的边,下图中A与B A与C就是直接相连的,而A和D不能直接到达而需要通过B和C所以不是直接相连的
第二步,在这些路径中找出一条长度最短的路径
第三步,然后对其余路径进行调整,若图中存在弧(u,vk) ,且(v0,u) + (u,vk) < (v0,vk),就以路径(v0,uvk)代替(v0,vk)。在调整后的各条路径中再找长度最短的路径,依次类推
Dijkstra算法的思想就是按照路径的长度递增的次序产生最短的路径
1、首先是把顶点集V分为两组
S:已经求出最短路径的顶点的集合
T = V - S :没有找到最短路径的顶点集合
2、把T中顶点按最短路径递增的次序加入到S中
同时保证从源点到S中各顶点的最短路径的长度都不大于从源点到到T中任何顶点的最短路径长度,每一个顶点都要对应一个距离值,S中顶点是从源点到此顶点最短路径的长度,T中顶点是从源点到此顶点的只包括S中顶点作中间顶点的最短路径。
当然上面的解释可能难以理解,下面我会用一个例子说明
T顶点对应的距离用辅助数组D存放,开始时,S中只有源点,T中有除源点外的其他顶点,如果v0到vi是直接相连的,D[i]为权值,如果不是则为无穷大,从T中选取一个距离值最小的顶点vj,加入S。对T中顶点的距离值进行修改,一直重复上述过程,直到S = V为止
代码实现,参考了网上
#include<iostream>
using namespace std;
const int INF=99999999; //无穷大数
int road[1000][1000]; //记录距离矩阵
int dist[1000]; //记录最短路径数组
bool visited[1005]; //记录是否已经搜过
//dijkstra最短路径算法,参数为顶点数目n、起始点start
void dijkstra(int n,int start)
{
dist[start]=0;
//依此遍历n个点,分别记录各点的最短路径
for(int i=0;i<n;i++)
{
int s=-1;//下标
int min=INF;//初始值
//找到没有搜过且距离最小的点
for(int j=0;j<n;j++)
{
if(visited[j]==false && dist[j]<min)
{
s=j;
min=dist[j];
}
}
if(s==-1) break;
else
{
visited[s]=true;
}
for(int v=0;v<n;v++)
{
//找到最短路径的话就更新
if(visited[v]==false && dist[s]+road[s][v]<dist[v] && road[s][v]!=INF)
{
dist[v]=dist[s]+road[s][v];
}
}
}
//分别输出起始点到每个点的最短路径
for(int i=0;i<n;i++)
{
cout<<dist[i]<<" ";
}
}
int main()
{
//输入n个城市、m条路径,以及开始搜索点
int n,m,start;
cin>>n>>m>>start;
//初始化,都定义为无穷大
fill(road[0],road[0]+1000*1000,INF);
fill(dist,dist+1000,INF);
//输入起点(a)、终点(b)、距离(c),并存入距离矩阵中
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
road[a][b]=c;
road[b][a]=c;
}
//调用函数
dijkstra(n,start);
system("pause");
return 0;
}
/*
测试用例
5 6 0
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
*/
评论(0)
您还未登录,请登录后发表或查看评论