迪杰斯特拉算法求助

li83126

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

li83126

li83126

高手给解答下，多谢

li83126

li83126

DAY

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

li83126

讲的有点含糊

li83126

lx_Zz

#include <cstdio>
#include <cstdlib>  
#include <cstring>
#include <cmath>
#include <vector>  
#include <queue>
#include <algorithm>  
using namespace std;  
#define inf 0x3f3f3f3f
  
const int maxn = 505;  
int dist[maxn];
struct node {
    int x, val;
    node(int a, int b) {x = a; val = b;}
    bool operator < (const node & a) const {
        if (val == a.val) return x < a.x;
        else return val > a.val;
    }
};
vector<node> v[maxn];

void Dijkstra(int s, int n) {
    for (int i = 1; i <= n; i++) dist[i] = inf;
    dist[s] = 0;
    priority_queue<node> q;
    q.push(node(s, dist[s]));
    while(!q.empty()) {
        node now = q.top(); q.pop();
        for (int i = 0; i < v[now.x].size(); i++) {
            node next = v[now.x][i];
            if (dist[next.x] > now.val + next.val) {
                dist[next.x] = now.val + next.val;
                q.push(node(next.x, dist[next.x]));
            }
        }
    }
    printf("%d\n", dist[n]);
}

int main() {  
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF, n + m) {
        for (int i = 1; i <= n; i++) v[i].clear();
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            v[a].push_back(node(b, c));
            v[b].push_back(node(a, c));
        }
        Dijkstra(1, n);
    }
    system("pause");
    return 0;  
}  

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

哥，厉害啊