迪杰斯特拉算法求助

li83126

这个里面的路径P怎么会是1 4 2 4 3 6 7  最短路径怎么有两个4，高手帮忙解答下，谢谢

li83126

li83126

高手给解答下，多谢

li83126

li83126

DAY

小甲鱼这集的视频没看懂，期待大神解答。。

li83126

讲的有点含糊

li83126

lx_Zz

1. #include <cstdio>
   
2. #include <cstdlib>  
   
3. #include <cstring>
   
4. #include <cmath>
   
5. #include <vector>  
   
6. #include <queue>
   
7. #include <algorithm>  
   
8. using namespace std;  
   
9. #define inf 0x3f3f3f3f
   
10.   
    
11. const int maxn = 505;  
    
12. int dist[maxn];
    
13. struct node {
    
14.     int x, val;
    
15.     node(int a, int b) {x = a; val = b;}
    
16.     bool operator < (const node & a) const {
    
17.         if (val == a.val) return x < a.x;
    
18.         else return val > a.val;
    
19.     }
    
20. };
    
21. vector<node> v[maxn];
    
22. 
    
23. void Dijkstra(int s, int n) {
    
24.     for (int i = 1; i <= n; i++) dist[i] = inf;
    
25.     dist[s] = 0;
    
26.     priority_queue<node> q;
    
27.     q.push(node(s, dist[s]));
    
28.     while(!q.empty()) {
    
29.         node now = q.top(); q.pop();
    
30.         for (int i = 0; i < v[now.x].size(); i++) {
    
31.             node next = v[now.x][i];
    
32.             if (dist[next.x] > now.val + next.val) {
    
33.                 dist[next.x] = now.val + next.val;
    
34.                 q.push(node(next.x, dist[next.x]));
    
35.             }
    
36.         }
    
37.     }
    
38.     printf("%d\n", dist[n]);
    
39. }
    
40. 
    
41. int main() {  
    
42.     int n, m;
    
43.     while(scanf("%d%d", &n, &m) != EOF, n + m) {
    
44.         for (int i = 1; i <= n; i++) v[i].clear();
    
45.         for (int i = 1; i <= m; i++) {
    
46.             int a, b, c;
    
47.             scanf("%d%d%d", &a, &b, &c);
    
48.             v[a].push_back(node(b, c));
    
49.             v[b].push_back(node(a, c));
    
50.         }
    
51.         Dijkstra(1, n);
    
52.     }
    
53.     system("pause");
    
54.     return 0;  
    
55. }  

复制代码

lx_Zz

最短路算法三言两语讲不清楚的、建议多百度
http://www.mengwuji.net/thread-6794-1-1.html

丹小怪

jerryxjr1220

带权重的最优路径算法，可以参考：
http://bbs.fishc.com/thread-81073-1-1.html
不过我是用python写的

CatC

赚鱼币有点慢啊，急需

西瓜小刚

lx_Zz 发表于 2016-8-3 17:36

哥，厉害啊