Skip to content

Instantly share code, notes, and snippets.

@tungurlakachakcak
Created September 14, 2022 12:12
Show Gist options
  • Save tungurlakachakcak/368e8e814dbfd96655b381766d47c4ee to your computer and use it in GitHub Desktop.
Save tungurlakachakcak/368e8e814dbfd96655b381766d47c4ee to your computer and use it in GitHub Desktop.
Dijkstra shortest path
#include <iostream>
#include <vector>
#include <math.h>
#include <unordered_map>
#include <string>
#include <fstream>
#include <stack>
#include <unordered_set>
#include <queue>
#include <stack>
#include <limits>
using namespace std;
struct Vertex {
Vertex(int value) : value(value), minDistance(numeric_limits<int>::max()), prev(nullptr) {}
int value;
int minDistance = numeric_limits<int>::max();
Vertex* prev;
};
struct Edge {
Vertex* start;
Vertex* end;
int weight;
};
class Comparator {
public:
bool operator()(Vertex* e1, Vertex* e2) const {
return e1->minDistance > e2->minDistance;
}
};
void dijkstraAll(unordered_map<int, vector<Edge*>>& g, unordered_map<int, Vertex*>& vertices) {
unordered_set<int> vis;
vector<Vertex*> pq;
for (auto& pair : vertices) {
pq.push_back(pair.second);
}
make_heap(pq.begin(), pq.end(), Comparator());
while (!pq.empty()) {
pop_heap(pq.begin(), pq.end(), Comparator());
Vertex* current = pq.back(); pq.pop_back();
// Going over all neighbors of the current vertex
for (Edge* edge : g[current->value]) {
// Update the distance to the neighbor if it's lower than the one it has so far.
int currentDistance = current->minDistance + edge->weight;
if (currentDistance < edge->end->minDistance) {
// Yes, the distance we calculated now is smaller than the one previously found. Update!
edge->end->minDistance = currentDistance;
edge->end->prev = current;
}
}
make_heap(pq.begin(), pq.end(), Comparator());
}
}
list<Vertex*> tracebackPath(Vertex* end) {
list<Vertex*> path;
Vertex* current = end;
while (current != nullptr) {
path.push_front(current);
current = current->prev;
}
return path;
}
int main() {
Vertex zero(0);
Vertex one(1);
Vertex two(2);
Vertex three{ 3 };
Vertex four{ 4 };
Vertex five{ 5 };
Vertex six{ 6 };
Vertex seven{ 7 };
Vertex eight{ 8 };
unordered_map<int, Vertex*> vertices = {
{ 0, &zero },
{ 1, &one },
{ 2, &two },
{ 3, &three },
{ 4, &four },
{ 5, &five },
{ 6, &six },
{ 7, &seven },
{ 8, &eight },
};
unordered_map<int, vector<Edge*>> graph;
int start, end;
cin >> start >> end;
// Setting the value of the starting vertex to 0 so that dijkstra starts from there.
vertices[start]->minDistance = 0;
graph[0].push_back(new Edge{ &zero, &one, 1 });
graph[0].push_back(new Edge{ &zero, &two, 8 });
graph[1].push_back(new Edge{ &one, &four, 2 });
graph[1].push_back(new Edge{ &one, &three, 1 });
graph[2].push_back(new Edge{ &two, &three, 2 });
graph[2].push_back(new Edge{ &two, &six, 4 });
graph[3].push_back(new Edge{ &three, &five, 9 });
graph[4].push_back(new Edge{ &four, &eight, 3 });
graph[5].push_back(new Edge{ &five, &eight, 7 });
graph[5].push_back(new Edge{ &five, &seven, 3 });
graph[6].push_back(new Edge{ &six, &seven, 1 });
dijkstraAll(graph, vertices);
cout << "Shortest path from start: " << start << " to " << end << " is " << vertices[end]->minDistance << endl;
for (Vertex* v : tracebackPath(vertices[end])) {
cout << v->value << " ";
}
cout << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment