Dijkstra算法求最短路
目录
Dijkstra
算法和Prim
算法具有极其相似的地方,二者都是构建两个集合,利用贪心算法,将其中一个集合不断进行扩充,最终求得最优解。
算法实现
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MAX_N = 1000, INF = 0x7ffffff;
int adj[MAX_N + 1][MAX_N + 1];
int distance[MAX_N + 1];
double minD[MAX_N + 1], graph[MAX_N][MAX_N];
bool visited[MAX_N + 1];
int t, n;
typedef pair<double, int> P;
double Dijkstra(int s, int len){
priority_queue<P, vector<P>, greater<P> > q;
fill(minD, minD + MAX_N, INF);
memset(visited, false, sizeof visited);
minD[s] = 0;
q.push(P(minD[s], s));
while(!q.empty()){
P front = q.top();
q.pop();
int u = front.second;
if(visited[u]) continue;
visited[u] = true;
for(int v = 1; v <= len; ++v){
if(minD[u] + graph[u][v] < minD[v]){
minD[v] = minD[u] + graph[u][v];
q.push(P(minD[v], v));
}
}
}
for (int i = 1; i <= len; i++) printf("%d ", minD[i]);
}
本文由「黄阿信」创作,创作不易,请多支持。
如果您觉得本文写得不错,那就点一下「赞赏」请我喝杯咖啡~
商业转载请联系作者获得授权,非商业转载请附上原文出处及本链接。
关注公众号,获取最新动态!
历史评论
开始评论