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

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

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

矩阵存储

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

#include 

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

{

for(int j=1; j

{

if( i==j )

{

//自己和自己的关系（权重）为 0

graph[i][j]=0;

}

else

{

//任意两点间的距离为无穷大

graph[i][j]=INF;

}

}

}

//交互式确定图中顶点之间的关系

int f,t,w;

for( int i=1; i

{

cin>>f>>t>>w;

graph[f][t]=w;

}

//初始设编号为 1 的顶点为起始点,根据顶点的关系初始化起点到其它顶点之间的距离

for(int i=1; i

{

dis[i]=graph[1][i];

}

//初始化优先队列（也称为候选队列）

for(int i=1; i

{

if(i==1)

{

//起始顶点默认为已经候选

pri[i]=1;

continue;

}

//其它顶点都可候选

pri[i]=0;

}

}

/*

*

*Dijkstra算法

*/

void dijkstra()

{

for(int i=1; i

{

//从候选队列中选择一个顶点，要求到起始顶点的距离为最近的

int u=-1;

int mi=INF;

for( int j=1; j

{

if(pri[j]==0 && dis[j]

{

mi=dis[j];

u=j;

}

}

if(u!=-1)

//找到后设置为已经候选

pri[u]=1;

else

//找不到就结束

break;

//查找与此候选顶点相邻的顶点，且更新邻接点与起点之间的距离

//相当于在此顶点基础上向后延长

for( int j=1; 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

{

cout

}

}

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 

using namespace std;

/*

* 顶点类型

*/

struct Ver

{

//顶点编号

int vid=0;

//第一个邻接点

int head=0;

//起点到此顶点的距离（顶点权重）,初始为 0 或者无穷大

int dis=0;

//重载函数

bool operator

{

return this->dis

}

void desc(){

cout

}

};

/*

* 边

*/

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 proQue;

public:

Graph( int v,int e )

{

this->v=v;

this->e=e;

init();

}

void init()

{

for(int i=1;i

//重置顶点信息

vers[i].vid=i;

vers[i].dis=INF;

vers[i].head=0;

}

int f,t,w;

for(int i=1; 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

{

dis[i]=vers[i].dis;

}

}

void dijkstra(int start)

{

//初始化优先队列,起点到起点的距离为 0

vers[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

{

cout

}

}

};

int main()

{

int v,e;

cin>>v>>e;

Graph graph(v,e);

int s;

cin>>s;

graph.dijkstra(s);

graph.show();

return 0;

}