Joyce' Blog
0%

使用优先队列的dijkstra和prim算法

发表于

复习时没有理解为什么使用优先队列的dijkstra和prim算法时间复杂度为O(mlogn)，专门拿出来学习一下。

dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
#define INF  0x3f3f3f3f   //定义一个很大的数

struct Node{
int num,val;   //存放结点编号和到初始点的距离 
}nod;
 
priority_queue<Node> qq;  //优先从小到大
bool operator < (Node a,Node b){
if(a.val == b.val) return a.num>b.num;
return a.val>b.val;              //先出小 
} 
int book[100];  //检查这个点是否用过 
int dis[100];     //到原点最短距离 
int D[100][100];  //记录路径长度
int V,E; 
 
int main(){
int a,b,d;
while(cin>>V>>E && V&& E)  //输入顶点数和边数 
{
while(!qq.empty()) qq.pop(); //清空
memset(book,0,sizeof(book));
memset(D,-1,sizeof(D));  
for(int i=0;i<E;i++){
cin>>a>>b>>d;
D[a][b] = D[b][a] = d;
}
for(int i=2;i<=V;i++)
dis[i]=INF;
 
dis[1]=0;
nod.num=1;
nod.val=0;
qq.push(nod);   //将起点放入队列 
 
while(!qq.empty()){ //每次排序需要logn的时间
for(int i=2;i<=V;i++){//更新距离
if(D[qq.top().num][i] != -1  &&dis[i]>dis[qq.top().num] + D[qq.top().num][i]) 
{//qq.top()的点与i连通并且有了更短的路径，这个条件最多进来m次，因为每条边只会被用最多一次。
dis[i]=dis[qq.top().num] + D[qq.top().num][i];
nod.num=i; nod.val=dis[i];
qq.push(nod);
}} 
qq.pop();
}
 
for(int i=1;i<=V;i++){
cout<<"初始点到"<<i<<"点的距离为："<<dis[i]<<endl;
}}
return 0;
}

原文：https://blog.csdn.net/jobsandczj/article/details/49962557

prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

const int N = 50 + 5, M = 5000 + 5;
int n, m;

struct Edge {
    int to, w;
    bool operator<(const Edge &other) const {
        return w > other.w;
    }
};

vector<Edge> v[N];
bool vis[N];

int Prime() {
    priority_queue<Edge> q;
    int cnt = 0, x, ans = 0;
    for (int i = 0; i < v[1].size(); ++i)q.push(v[1][i]);
    vis[1] = 1;
    while (cnt < n - 1) {
        Edge e = q.top();//排序每次需要logn的时间
        q.pop();
        x = e.to;
        if (!vis[x]) {//最多走m条边
            vis[x] = 1;
            ans += e.w, cnt++;
            for (int i = 0; i < v[x].size(); ++i)q.push(v[x][i]);
        }
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, w;
        cin >> x >> y >> w;
        v[x].push_back(Edge{y, w});
        v[y].push_back(Edge{x, w});
    }
    cout << Prime() << endl;
    return 0;
}