C++ Dijkstra 最短路径求解算法的两种实现方案

迪杰斯特拉算法(Diikstra) 是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。

核心思想，搜索到某一个顶点后，更新与其相邻顶点的权重。顶点权重的数据含义表示从起始点到此点的最短路径长度（也就是经过的所有边的权重之和）。DJ 算法搜索时，每次选择的下一个顶点是所有权重值最小的顶点，其思想是保证每一次选择的顶点和当前顶点权重都是最短的。所以，DJ是基于贪心思想。

矩阵存储

常规时间复杂度：O(n)，可以使用堆优化优先队列，时间复杂度降低到O(logN)。缺点是对于稀疏图而言空间浪费严重。

#include <bits/stdc++.h>
using namespace std;//矩阵，存储图
int graph[100][100];
//顶点、边数
int v,e;
//优先队列，使用数组
int pri[100];
//存储起点到其它顶点之间的最短距离
int dis[100];
//设置无穷大常量
int const INF =INT_MAX;/*
*初始化函数
*/
void init()
{//初始化图中顶点之间的关系for(int i=1; i<=v; i++){for(int j=1; j<=v; j++){if( i==j ){//自己和自己的关系（权重）为 0graph[i][j]=0;}else{//任意两点间的距离为无穷大graph[i][j]=INF;}}}//交互式确定图中顶点之间的关系int f,t,w;for( int i=1; i<=e; i++ ){cin>>f>>t>>w;graph[f][t]=w;}//初始设编号为 1 的顶点为起始点,根据顶点的关系初始化起点到其它顶点之间的距离for(int i=1; i<=v; i++){dis[i]=graph[1][i];}//初始化优先队列（也称为候选队列）for(int i=1; i<=v; i++ ){if(i==1){//起始顶点默认为已经候选pri[i]=1;continue;}//其它顶点都可候选pri[i]=0;}}/*
*
*Dijkstra算法
*/
void dijkstra()
{for(int i=1; i<=v; i++){//从候选队列中选择一个顶点，要求到起始顶点的距离为最近的int u=-1;int mi=INF;for( int j=1; j<=v; j++ ){if(pri[j]==0 && dis[j]<mi){mi=dis[j];u=j;}}if(u!=-1)//找到后设置为已经候选pri[u]=1;else //找不到就结束break;//查找与此候选顶点相邻的顶点，且更新邻接点与起点之间的距离//相当于在此顶点基础上向后延长for( int j=1; j<=v; j++ ){if(  graph[u][j]!=INF ){//找到相邻顶点if(dis[j]>dis[u]+graph[u][j]  ){//更新dis[j]=dis[u]+graph[u][j];}}}}}/*
*
*显示最后的结果
*/
void show()
{for(int i=1; i<=v; i++){cout<<dis[i]<<"\t";}
}int main()
{cin>>v>>e;init();dijkstra();show();return 0;
}
//测试用例
6  9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
//输出
0  1  8  4  13  17

邻接表

整个时间复杂度可以优化到O(M+N)logN。在最坏的情况下M(边数)就是N（顶点数），这样的话(M+M)logN要比N还要大。但是大多数情况下并不会有那么多边，因此(M+M)logN要比N小很多。

#include <bits/stdc++.h>using namespace std;
/*
* 顶点类型
*/
struct Ver
{//顶点编号int vid=0;//第一个邻接点int head=0;//起点到此顶点的距离（顶点权重）,初始为 0 或者无穷大int dis=0;//重载函数bool operator<( const Ver & ver ) const{return this->dis<ver.dis;}void desc(){cout<<vid<<" "<<dis<<endl;}
};/*
* 边
*/
struct Edge
{//邻接点int to;//下一个int next=0;//权重int weight;
};class Graph
{
private:const int INF=INT_MAX;//存储所有顶点Ver vers[100];//存储所有边Edge edges[100];//顶点数，边数int v,e;//起点到其它顶点之间的最短距离int dis[100];//优先队列priority_queue<Ver> proQue;public:Graph( int v,int e ){this->v=v;this->e=e;init();}void init(){for(int i=1;i<=v;i++){//重置顶点信息vers[i].vid=i;vers[i].dis=INF;vers[i].head=0;}int f,t,w;for(int i=1; i<=e; i++){cin>>f>>t>>w;//设置边的信息edges[i].to=t;edges[i].weight=w;//头部插入edges[i].next=vers[f].head;vers[f].head=i;}for(int i=1; i<=v; i++){dis[i]=vers[i].dis;}}void dijkstra(int start){//初始化优先队列,起点到起点的距离为 0vers[start].dis=0;dis[start]=0;proQue.push(vers[start]);while( !proQue.empty() ){//出队列Ver ver=proQue.top();ver.desc();proQue.pop();//找到邻接顶点 i 是边集合索引号for( int i=ver.head; i!=0; i=edges[i].next){int v=edges[i].to;//更新距离if( vers[ v ].dis > ver.dis + edges[i].weight ){vers[ v ].dis = ver.dis+edges[i].weight;dis[ v ]= vers[ v ].dis;//入队列proQue.push( vers[v] );}}}}void show(){for(int i=1; i<=v; i++){cout<<dis[i]<<"\t";}}};int main()
{int v,e;cin>>v>>e;Graph graph(v,e);int s;cin>>s;graph.dijkstra(s);graph.show();return 0;
}