li83126 发表于 2016-7-14 09:10:28

迪杰斯特拉算法求助



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

li83126 发表于 2016-7-14 10:10:45

本帖最后由 li83126 于 2016-7-14 12:32 编辑

{:5_91:}

li83126 发表于 2016-7-15 10:55:34

高手给解答下，多谢

li83126 发表于 2016-7-19 15:47:11

{:10_249:}

li83126 发表于 2016-7-19 15:47:43

{:10_249:}

DAY 发表于 2016-7-19 16:37:02

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

li83126 发表于 2016-7-21 14:34:38

讲的有点含糊

li83126 发表于 2016-7-25 21:19:25

{:10_249:}

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

#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;
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;

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

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

lx_Zz 发表于 2016-8-3 17:40:03

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

丹小怪 发表于 2016-8-10 22:43:21

{:5_99:}

jerryxjr1220 发表于 2017-1-5 10:06:21

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

CatC 发表于 2017-1-7 00:58:15

赚鱼币有点慢啊，急需

西瓜小刚 发表于 2017-1-7 11:11:20

学习

本帖最后由 西瓜小刚 于 2021-9-13 09:46 编辑

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


哥，厉害啊{:7_113:}
页: [1]
查看完整版本: 迪杰斯特拉算法求助