最短路 Dijkstra算法

概述最短路 Dijkstra算法

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

最短路的最优子结构性质 未优化的Dijkstra算法代码

int cost[max_v][max_v]; //使用邻接矩阵储存边(不存在就是INF)int d[max_v]; //最短距离bool used[max_v]; //已经确定最短路的图int V;//Dijkstra算法voID dijkstra(int s){    //初始化    fill(d,d+V,INF);    fill(used,used+V,false);    d[s] = 0;    //最短路    while(true) {        int v = -1;        for(int i = 0 ; i < V ; i ++) {            if(!used[i]) {                if(v == -1 || d[i] < d[v]) v = i;            }        }        if(v == -1) break;//如果都确定了就退出        used[v] = true;        for(int i = 0 ; i < V ; i ++) {            d[i] = min(d[i],d[v]+cost[v][i]);        }    }}

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct edge{int to,cost;};typedef pair<int,int> P; //first是最短距离 second是顶点编号int V;vector<edge> G[max_v];//邻接表int d[max_v];voID dijkstra(int s){    //通过指定greater<P>参数，堆按照first从小到大的顺序取出值    priority_queue<P,vector<P>,greater<P>> que;    fill(d,INF);    d[s] = 0;    que.push(P(0,s));    while(!que.empty()) {        P p = que.top();        que.pop();        int v = p.second;//编号        if(d[v] < p.first) continue;        for(int i = 0 ; i < G[v].size() ; i ++) {            edge e = G[v][i];            if(d[e.to] > d[v]+e.cost) {                d[e.to] = d[v]+e.cost;                que.push(P(d[e.to],e.to));            }        }    }}

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的最短路 Dijkstra算法全部内容，希望文章能够帮你解决最短路 Dijkstra算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。