首页 > 代码库 > 最短路径算法之二——Dijkstra算法

最短路径算法之二——Dijkstra算法

2024-07-13 14:45:37   225人阅读

Dijkstra算法

　　Dijkstra算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

　　注意该算法要求图中不存在负权边。

　　首先我们来定义一个二维数组Edge[MAXN][MAXN]来存储图的信息。

 

　　　　这个图的Edge数组初始化以后为

 

　　　　我们还需要用一个一维数组dis来存储1号顶点到其余各个顶点的初始路程，如下。

 

　　这个dis数组中存的是最短路的估计值。

　　通过Dijkstra算法来松弛后，dis存的为从初始点到各点的精确值(最短路径)了。

 

Dijkstra算法实现如下(以HDU1548为例):

 

 1 #include<stdio.h> 2 #include<limits.h> 3 #include<iostream> 4 #include<string.h> 5 #define MAXN 200 6 using namespace std; 7 int edge[MAXN+10][MAXN+10]; 8 int dis[MAXN+10]; 9 bool vis[MAXN+10];10 int T,S,D,N,k;11 void dijkstra(int begin)12 {13     memset(vis,0,sizeof(vis));14     for (int i=1; i<=T; i++)15         dis[i]=INT_MAX;16     dis[begin]=0;17     for (int t=1; t<=T; t++)18     {19         vis[begin]=1;20         for (int i=1; i<=T; i++)21             if (!vis[i]&&edge[begin][i]!=INT_MAX&&dis[begin]+edge[begin][i]<dis[i])22                 dis[i]=dis[begin]+edge[begin][i];23         int min=INT_MAX;24         for (int j=1; j<=T; j++)25             if (!vis[j]&&min>dis[j])26             {27                 min=dis[j];28                 begin=j;29             }30     }31 }32 int main()33 {34     int begin,end;35     while (cin>>T)36     {37         if (T==0) break;38         for (int i=1; i<=MAXN; i++)39             for (int j=1; j<=MAXN; j++)40                 edge[i][j]=INT_MAX;41         scanf("%d %d",&begin,&end);42         int t;43         for (int i=1; i<=T; i++)44         {45             scanf("%d",&t);46             if (i+t<=T) edge[i][i+t]=1;47             if (i-t>=1) edge[i][i-t]=1;48         }49         dijkstra(begin);50         if (dis[end]!=INT_MAX) printf("%d\n",dis[end]);51         else printf("-1\n");52     }53     return 0;54 }

 

时间复杂度：O(N^2)

使用邻接表(见下文)优化后可达到O(MlogN) 

PS：M在最坏情况下可能为N^2!!

部分图片文字摘自于啊哈磊的blog。

 


联系
我们