Skip to content

Instantly share code, notes, and snippets.

@lsem

lsem/dijkstra.cpp

Last active July 31, 2024 18:40
Show Gist options
  • Save lsem/49f0f3d8b91fee2bcc18cb6c869af320 to your computer and use it in GitHub Desktop.
Save lsem/49f0f3d8b91fee2bcc18cb6c869af320 to your computer and use it in GitHub Desktop.
Download ZIP
dijkstra.cpp
Raw
dijkstra.cpp
#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using VertexID = string;
using Weight = int;
struct Vertex {
VertexID id;
};
using Graph = map<VertexID, vector<tuple<VertexID, Weight>>>;
map<VertexID, Weight> find_shortest_path(const Graph &graph, VertexID from) {
list<VertexID> queue;
Weight current_path_length = 0;
map<VertexID, Weight> dist;
for (auto &[n, _] : graph) {
dist[n] = std::numeric_limits<Weight>::max();
queue.emplace_back(n);
}
dist[from] = 0;
set<VertexID> visited;
while (!queue.empty()) {
list<VertexID>::const_iterator min_it = queue.begin();
Weight min = std::numeric_limits<Weight>::max();
for (auto it = queue.begin(); it != queue.end(); ++it) {
auto w = dist[*it];
if (w < min) {
min = w;
min_it = it;
}
}
assert(min_it != queue.end());
VertexID curr = *min_it;
current_path_length = dist[curr];
queue.erase(min_it);
visited.insert(curr);
if (const auto it = graph.find(curr); it != graph.end()) {
for (auto &[v, w] : it->second) {
if (visited.count(v) == 0) {
if (current_path_length + w < dist[v]) {
dist[v] = current_path_length + w;
}
}
}
}
}
return std::move(dist);
}
int main() {
Graph g;
auto add_connection = [&g](VertexID x, VertexID y, Weight w) {
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
};
add_connection("A", "B", 1);
add_connection("A", "C", 10);
add_connection("B", "C", 2);
for (auto &[v, w] : find_shortest_path(g, "A")) {
std::cout << v << ": " << w << "\n";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment