Dijkstra
特点:权值非负、单源、有向和无向、无优化O(n2),使用优先队列优化O(mlogn)
//
// main.cpp
// Dijkstra无优化
//
// Created by Haoying Zhao on 17/8/28.
// Copyright © 2017年 Haoying Zhao. All rights reserved.
//
#include <iostream>
using namespace std;
#define N 6
#define MAX 101
int find_min_position(int* mindis, int* flag) {
int min = MAX;
int pos = -1;
for(int i = 0; i < N; i++) {
if(flag[i] == 1)
continue;
if(mindis[i] < min) {
min = mindis[i];
pos = i;
}
}
return pos;
}
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 flag[N];
memset(flag, 0, sizeof(flag));
int mindis[N];
for(int i = 0; i < N; i++)
mindis[i] = MAX;
int parent[N];
memset(parent, 0 , sizeof(parent));
mindis[0] = 0;
for(int j = 0; j < N; j++) {
int pos = find_min_position(mindis, flag);
flag[pos] = 1;
int dis = mindis[pos];
for(int i = 0 ; i < N; i++) {
if(flag[i] == 1)
continue;
if(a[pos][i] == MAX)
continue;
if(mindis[i] > dis + a[pos][i]) {
mindis[i] = dis + a[pos][i];
parent[i] = pos;
}
}
}
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;
}
输出结果:
mindis:
0 5 3 6 7 9
parent:
0 2 0 2 2 3
track:
A
B<---C<---A
C<---A
D<---C<---A
E<---C<---A
F<---D<---C<---A