Dijkstra

1,核心思想：

 Dijkstra算法是典型的最短路径算法，用于计算一个顶点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

2，算法流程:

 

举例从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的权值，d[i]即为最短路径。

1，置集合S={2,3,…n},数组d(1)=0,d(i)=W1->i,(1,i 之间存在边)，否则为无穷大。

2，在S中，令d(j)=min{d(i),i属于S}，令S=S-{j},若S为空集则结束，否则转3

3，对全部i属于S，如果存在边jài，那么置d(i)=min{d(i),d(j)+Wj->i}，转2

 

3，复杂度：

时间复杂度：O（n^2）;

空间复杂度：O（n^2）；

4，核心代码：

Dist[i]表示从start 到 i 的 最短路径，Visit[i] 表示 i 点已访问过，已经为从start 到 i 的最短路径。

void Dijkstra(int start,int n) { int i,j,k; int Dist[]; bool Visted[]; for(i=1;i<=n;i++) { Dist[i]=map[start][i]; Visted[i]=0; } Dist[start]=0; Visted[start]=1;//初始化 for(i=1;i<n;i++) { int min=INF; k=-1; for(j=1;j<=n;j++) { if(Visted[j]==0&&Dist[j]<min) { min=Dist[j]; k=j; } }//找到最小的 if(k!=-1) { Visted[k]=1; for(j=1;j<=n;j++) { if(Dist[k]+map[k][j]<Dist[j]) Dist[j]=Dist[k]+map[k][j]; }// 确定最小的后再连接出去的。 } } }

5,标记路径

 上面所给出的代码只是简单地计算出最短路径的值，如果要记录路径，再开一个pre[]记录走过的节点即可。

void Dijkstra(int start,int n) { int i,j,k; int Dist[]; bool Visted[]; for(i=1;i<=n;i++) { Dist[i]=map[start][i]; Visted[i]=0; if(Dist[i]<INF) pre[i] = start; else pre[i]=-1;//初始时均赋值为-1 } Dist[start]=0; Visted[start]=1;//初始化 for(i=1;i<n;i++) { int min=INF; k=-1; for(j=1;j<=n;j++) { if(Visted[j]==0&&Dist[j]<min) { min=Dist[j]; k=j; } }//找到最小的 if(k!=-1) { Visted[k]=1;//标记掉 for(j=1;j<=n;j++) { if(Dist[k]+map[k][j]<Dist[j]) { Dist[j]=Dist[k]+map[k][j]; pre[j]=k; } }// 确定最小的后再连接出去的。 } } }

 

6,TipS：Dijkstra算法不适用于权值有负值的情况。