使用优先队列优化：
只是对点的选择起作用，mindis数组仍保留。
//
// main.cpp
// Dijkstra_priorityqueue
//
// Created by Haoying Zhao on 17/8/29.
// Copyright © 2017年 Haoying Zhao. All rights reserved.
//
#include <iostream>
#include <queue>
using namespace std;
#define N 6
#define MAX 101
typedef pair<int, int> point;
struct cmp {
bool operator ()(const point A, const point B) {
if(A.second == B.second)
return A.first < B.first;
return A.second > B.second;
}
};
int main(int argc, const char * argv[]) {
int a[N][N];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(i != j) a[i][j] = MAX;
else a[i][j] = 0;
a[0][1] = 6; a[1][0] = 6;a[0][2] = 3; a[2][0] = 3;
a[1][2] = 2; a[2][1] = 2;a[1][3] = 5; a[3][1] = 5;
a[2][3] = 3; a[3][2] = 3;a[2][4] = 4; a[4][2] = 4;
a[3][5] = 3; a[5][3] = 3;a[3][4] = 2; a[4][3] = 2;
a[4][5] = 5; a[5][4] = 5;
int mindis[N];
for(int i = 0; i < N; i++)
mindis[i] = MAX;
priority_queue<point,vector<point>,cmp> point_queue;
point_queue.push(make_pair(0, 0));
int parent[N];
memset(parent, 0, sizeof(parent));
int flag[N];
memset(flag, 0, sizeof(flag));
while(!point_queue.empty()) {
point pos = point_queue.top();
point_queue.pop();
if(flag[pos.first] == 1)
continue;
flag[pos.first] = 1;
for(int i = 0 ; i < N; i++) {
if(a[pos.first][i] == MAX)
continue;
if(mindis[i] > pos.second + a[pos.first][i]) {
mindis[i] = pos.second + a[pos.first][i];
parent[i] = pos.first;
point_queue.push(make_pair(i,mindis[i]));
}
}
}
cout << "mindis: " << endl;
for(int i = 0; i < N; i++)
cout << mindis[i] << " ";
cout << endl << "parent: " << endl;
for(int i = 0; i < N; i++)
cout << parent[i] << " ";
cout << endl << "track: " << endl;
for(int i = 0; i < N; i++) {
cout << (char)('A'+i);
int j = i;
while(1) {
if(j == 0)
break;
cout << "<---" << (char)('A'+parent[j]);
j = parent[j];
}
cout << endl;
}
return 0;
}
反思：
1、优先队列的pop返回值是void，需要先top再pop。
2、此题优先队列中插入了很多多余点，比如两个点先后作为parent给第三点更新最小距离，则会插入两次。多余的点因为排在最优元素之后均不能更新其他点，因此出队时不会造成影响。使用flag可以避免查找，减枝。
3、优先队列的排序问题：
1）直接把需要排序的值放前，使用greater和less调节。
2）定义类，重载运算符<。使用class，须在public:下，struct则不用。
#include <iostream>
#include <queue>
using namespace std;
class point {
public:
int x;
point(int t) {
x = t;
}
bool operator < (const point A) const {
return this->x > A.x;
}
};
int main(int argc, const char * argv[]) {
priority_queue<point> xx;
xx.push(point(5));
xx.push(point(4));
xx.push(point(3));
int i = 0;
while(!xx.empty()) {
i++;
cout << i << ": " << xx.top().x << endl;
xx.pop();
}
return 0;
}
友元函数：
#include <iostream>
#include <queue>
using namespace std;
class point {
public:
int x;
point(int t) {
x = t;
}
friend bool operator < (const point A, const point B) {
return A.x > B.x;
}
};
int main(int argc, const char * argv[]) {
priority_queue<point> xx;
xx.push(point(5));
xx.push(point(4));
xx.push(point(3));
int i = 0;
while(!xx.empty()) {
i++;
cout << i << ": " << xx.top().x << endl;
xx.pop();
}
return 0;
}
3）新建struct，重载运算符()。
#include <iostream>
#include <queue>
using namespace std;
struct cmp {
bool operator ()(const int A, const int B) {
return A > B;
}
};
int main(int argc, const char * argv[]) {
priority_queue<int,vector<int>,cmp> x;
x.push(5);
x.push(3);
x.push(4);
int i = 0;
while(!x.empty()) {
i++;
cout << i << ": " << x.top() << endl;
x.pop();
}
return 0;
}
使用邻接矩阵：
//
// main.cpp
// dijkstra2
//
// Created by Haoying Zhao on 17/8/29.
// Copyright © 2017年 Haoying Zhao. All rights reserved.
//
#include <iostream>
#include <queue>
using namespace std;
#define N 6
#define MAX 101
typedef pair<int, int> point;
int main(int argc, const char * argv[]) {
vector<point> a[N];
a[0].push_back(make_pair(6, 1));a[1].push_back(make_pair(6, 0));
a[0].push_back(make_pair(3, 2));a[2].push_back(make_pair(3, 0));
a[1].push_back(make_pair(2, 2));a[2].push_back(make_pair(2, 1));
a[1].push_back(make_pair(5, 3));a[3].push_back(make_pair(5, 1));
a[2].push_back(make_pair(3, 3));a[3].push_back(make_pair(3, 2));
a[2].push_back(make_pair(4, 4));a[4].push_back(make_pair(4, 2));
a[3].push_back(make_pair(3, 5));a[5].push_back(make_pair(3, 3));
a[3].push_back(make_pair(2, 4));a[4].push_back(make_pair(2, 3));
a[4].push_back(make_pair(5, 5));a[5].push_back(make_pair(5, 4));
int mindis[N];
int flag[N];
int parent[N];
memset(flag, 0, N);
for(int i = 0; i < N; i++)
mindis[i] = MAX;
mindis[0] = 0;
memset(parent, 0, N);
priority_queue<point,vector<point>,greater<point>> q;
q.push(make_pair(0, 0));
while(!q.empty()) {
point x = q.top();
q.pop();
if(flag[x.second] == 1)
continue;
flag[x.second] = 1;
for(vector<point>::iterator it = a[x.second].begin(); it != a[x.second].end(); ++it) {
if(mindis[it->second] > x.first + it->first) {
mindis[it->second] = x.first + it->first;
parent[it->second] = x.second;
q.push(make_pair(mindis[it->second], it->second));
}
}
}
for(int i = 0; i < N; i++)
cout << mindis[i] << " ";
cout << endl;
for(int i = 0; i < N; i++) {
cout << (char)('A'+i);
int m = parent[i];
while(1) {
cout << "<----" << (char)(m+'A');
if(m == 0) break;
m = parent[m];
}
cout << endl;
}
return 0;
}
