华师一附中OI组

标题: Dijkstra方法求最短路径 [打印本页]

---

作者: diggersun    时间: 2015-11-1 23:44
标题: Dijkstra方法求最短路径


经典的贪心方法，或者叫启发式广度优先搜索，尽管现在人们更喜欢SPFA，但是还是了解一下它吧。TYVJ1031 热浪，经典的题目，我的做法：

1. #include <iostream>
   
2. using namespace std;
   
3. int g[2600][2600];
   
4. bool flag[2600];
   
5. int rount[2600];
   
6. int T, C, Ts, Te, rs, re, ci;
   
7. int FindMin()//找所有的未标号的顶点中路径的最小值
   
8. {
   
9.     int Min,Temp,i;
   
10.     Min=999999999;
    
11.     for (i=1; i<=T; i++)
    
12.         if ((!flag[i]) &&(rount[i]<Min))
    
13.         {
    
14.             Temp=i;
    
15.             Min=rount[i];
    
16.         }
    
17.     return Temp;
    
18. }
    
19. int main()
    
20. {
    
21. 
    
22.     int i,j,k;
    
23.     int shortest;
    
24.     cin >> T >> C >> Ts >> Te;
    
25.     for (i=1; i<=T; i++)
    
26.     {
    
27.         rount[i]=999999999;
    
28.         for (j=i; j<=T; j++)
    
29.             g[i][j]=g[j][i]=999999999;
    
30.     }
    
31.     for (i = 1; i <= C; i++)
    
32.     {
    
33.         cin >> rs >> re >> ci;
    
34.         if (ci<g[rs][re]) g[rs][re]= g[re][rs] = ci;
    
35.     }
    
36.     flag[Ts]=1;
    
37.     i=Ts;//从第一顶点开始
    
38.     rount[i]=0;
    
39.     do
    
40.     {
    
41.         shortest=99999999;
    
42.         for (j=1; j<=T; j++)
    
43.             if (!flag[j])   //本点没有被标号
    
44.                 if (rount[j]>rount[i]+g[i][j])
    
45.                     rount[j]=rount[i]+g[i][j];
    
46.         i=FindMin();
    
47.         flag[i]=1;
    
48.     }
    
49.     while (!flag[Te]);
    
50.     cout<<rount[Te];
    
51.     return 0;
    
52. }
    

复制代码

---

作者: diggersun    时间: 2015-11-1 23:45
变形还是很多的，比如，求次短的路径。

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2