Dijkstra
#include <iostream>
#include <iomanip>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> paired;
void printMatrix2(int matrix[7][7], string nodes[7])
{
cout << setw(10) << " |";
for (int r=0; r<7; r++)
{
cout << setw(6) << nodes[r] << " |";
}
cout << endl;
for (int r=0; r<70; r++)
{
cout << "-";
}
cout << endl;
for (int r=0; r<7; r++)
{
cout <<setw(8) << nodes[r] << " |";
for (int c=0; c<7; c++)
{
cout << setw(6) << matrix[r][c] << " |";
}
cout << endl;
}
}
vector<int> initDistance(int matrix[7][7], int spos)
{
vector<int> dist;
for (int i=0; i < 7; i++)
{
if (i == spos)
dist.push_back(0);
else
dist.push_back(INT_MAX);
// cout << dist[i] << endl;
}
return dist;
}
void Dijkstra(int matrix[7][7], int spos, string nodes[7])
{
vector<int> parent{-1, -1, -1, -1, -1, -1, -1};
priority_queue<paired, vector<paired>, greater<paired>> visit; // set order rule
vector<int> visited;
vector<int> dist = initDistance(matrix, spos);
visit.push({0, spos});
parent[spos] = spos;
while (!visit.empty())
{
paired current_paired = visit.top();
int current_dest = current_paired.first;
int current_pos = current_paired.second;
visit.pop();
visited.push_back(current_pos);
// cout << "Current pos: " << current_pos << " " << visit.size() << visited.size() << endl;
for (int i=0; i < 7; i++)
{
if (i == current_pos or matrix[current_pos][i] == 0) continue;
else
{
if (find(visited.begin(), visited.end(), i) != visited.end())
continue;
else
{
if (dist[current_pos] + matrix[current_pos][i] < dist[i])
{
dist[i] = dist[current_pos] + matrix[current_pos][i];
visit.push(make_pair(dist[i], i));
parent[i] = current_pos;
}
}
}
}
}
// print result
for (int i=0; i <7; i++)
cout << nodes[i] << " : " << dist[i] << "(" << nodes[parent[i]] << "), ";
cout << endl;
}
int dijkstraMain()
{
string nodes[] = {"A", "B", "C", "D", "E", "F", "G"};
int spos = 0;
int matrix[7][7] = {
{0, 12, 0, 0, 0, 16, 14},
{12, 0, 10, 0, 0, 7, 0},
{0, 10, 0, 3, 5, 6, 0},
{0, 0, 3, 0, 4, 0, 0},
{0, 0, 5, 4, 0, 2, 8},
{16, 7 , 6, 0, 2, 0, 9},
{14, 0, 0, 0, 8, 9, 0}
};
printMatrix2(matrix, nodes);
cout << endl;
Dijkstra(matrix, spos, nodes);
return 0;
}
/* result reference
| A | B | C | D | E | F | G |
----------------------------------------------------------------------
A | 0 | 12 | 22 | 22 | 18 | 16 | 14 |
B | 12 | 0 | 10 | 13 | 9 | 7 | 16 |
C | 22 | 10 | 0 | 3 | 5 | 6 | 13 |
D | 22 | 13 | 3 | 0 | 4 | 6 | 12 |
E | 18 | 9 | 5 | 4 | 0 | 2 | 8 |
F | 16 | 7 | 6 | 6 | 2 | 0 | 9 |
G | 14 | 16 | 13 | 12 | 8 | 9 | 0 |
start form A -> A : 0(A), B : 12(A), C : 22(B), D : 22(E), E : 18(F), F : 16(A), G : 14(A),
*/
