初学算法之dijkstra

　　dijkstra的代码思想网上各路高手所述备矣。这里只是存下用邻接矩阵和邻接表实现的dijkstra。（白书代码）

　　邻接矩阵

 1 void dijkstra(int s){

 2     int dis[s]=0;

 3     while(1){

 4         int v=0;  //从尚未使用过的顶点中选择一个距离最小的顶点

 5         for(int u=1;u<=n;u++){

 6             if(!used[u]&&dis[v]>dis[u])

 7             v=u;

 8         }

 9         if(!v) break;

10         used[v]=1;

11         for(int u=1;u<=n;u++){

12             dis[u]=min(dis[u],dis[v]+dis[v][u]);

13         }

14     }

15 }

　　　　堆优化的dijkstra

 1 struct edge{int to,cost;};

 2 typedef pair<int ,int > P;

 3

 4 int V;

 5 vector<int>G[Max];

 6 int d[Max];

 7

 8 void dijkstra(int s){

 9     priority_queue<P>,vector<P>,greater<P> >que;//通过指定greater<P>参数

10     que.push(P(0,s));                             //堆按照first从小到大的顺序取出值

11

12     while(!que.empty()){

13         P p=que.top();que.pop();

14         int v=p.second;

15         if(d[v]<p.first) continue;

16         for(int i=0;i<G[v].size();i++){

17             edge e=G[v][i];

18             if(d[e.to]>d[v]+e.cost){

19                 d[e.to]=d[v]+e.cost;

20                 que.push(P(d[e.to],e.to));

21             }

22         }

23     }

24 }

25

26

例题：hdu-2544 最短路

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间Sample Input

Sample Output

3

2

这题就是单纯的套模板
附本人堆优化dijkstra的ac代码

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <queue>

 4 #include <vector>

 5 const int Max = 111111;

 6 const int inf = 0x3f3f3f3f;

 7 using namespace std;

 8 struct edge{int to,cost;};

 9 vector<edge>G[Max];

10 int d[Max];

11 typedef pair<int,int>P;

12 void dijkstra(){

13     priority_queue<P,vector<P>,greater<P> >que;

14     d[0]=0;

15     que.push(P(0,0));

16     while(!que.empty()){

17         P p=que.top();que.pop();

18 //        printf("%d ",p.first);

19         int v=p.second;

20         if(d[v]<p.first) continue;

21         for(int i=0;i<G[v].size();i++){

22             edge e=G[v][i];

23             if(d[e.to]>d[v]+e.cost){

24 //                printf("%d ",d[e.to]);

25                 d[e.to]=d[v]+e.cost;

26                 que.push(P(d[e.to],e.to));

27             }

28         }

29     }

30 }

31 int main(){

32     int n,m;

33     while(~scanf("%d %d",&n,&m),n+m){

34         memset(d,inf,sizeof(d));

35         int a,b,c;

36         for(int i=0;i<m;i++){

37             scanf("%d %d %d",&a,&b,&c);

38             a-=1;

39             b-=1;

40             edge e;

41             e.to=b;e.cost=c;

42             G[a].push_back(e);

43             e.to=a;

44             G[b].push_back(e);

45         }

46         dijkstra();

47         printf("%d\n",d[n-1]);

48         for(int i=0;i<m;i++)

49         G[i].clear();

50     }

51     return 0;

52 }

附本人邻接矩阵的ac代码

 1 #include<cstdio>

 2 #include<cstring>

 3 #include<vector>

 4 #include<algorithm>

 5 #include<iostream>

 6 #include<queue>

 7

 8 using namespace std;

 9

10 const int inf = 0x3f3f3f3f;

11

12 int mp[105][105],dis[105],used[105],n;

13

14 void dijkstra(){

15     for(int i=1;i<=n;i++){

16         dis[i]=mp[1][i];

17     }

18 //    for(int i=1;i<=n;i++)

19 //            cout << mp[1][i] <<endl;

20     dis[1]=0;

21     used[1]=1;

22     while(1){

23         int minn=inf,u=-1;

24         for(int i=1;i<=n;i++){

25             if(minn>dis[i]&&used[i]==0){

26                 minn=dis[i];

27                 u=i;

28             }

29         }

30         used[u]=1;

31         if(u==-1)    break;

32         for(int i=1;i<=n;i++){

33             int temp=min(inf,dis[u]+mp[u][i]);

34             if(dis[i]>temp){

35                 dis[i]=temp;

36             }

37         }

38     }

39 }

40 int main(){

41     ios::sync_with_stdio(false);

42     int m,i,j,a,b,c;

43     while(cin >> n >> m,n||m){

44         memset(dis,0,sizeof(dis));

45         memset(mp,inf,sizeof(mp));

46         memset(used,0,sizeof(used));

47         for(i=0;i<m;i++){

48             cin >> a >> b >> c;

49             mp[a][b] = c;

50             mp[b][a] = c;

51         }

52         dijkstra();

53

54         cout << dis[n] << endl;

55     }

56     return 0;

57 }

巴特西

初学算法之dijkstra

最新文章

热门文章