Translating Dijkstra's Algorithm from Python to C++

Question

I'm going through the book Grokking Algorithms which is in Python but wanted to write everything in C++. Up to this point everything's been pretty straightforward translation but the code for Dijkstra's algorithm really exploits nested dictionaries and weak typing which I used as an excuse to try out std::optional. I also am playing around with std::set, std::unordered_map, and using typedef to alias ugly types for the first time.

I've retained the original script-like functionality of the original code and have thrown everything into main, and know that a real implementation would be nicely put into a separate function. I am also aware that a real implementation would use a priority queue for finding the minimum cost edge rather than a linear search and wasn't really interested in Dijkstra's but moreso in the C++.

What to Review

Primarily interested in knowing about my usage of typedef in this way, as well as if there was a better way than using std::optional and std::nullopt to handle translating from Python's None type.

C++17 Code

Translated from Python from Grokking Algorithms book.

#include <algorithm>
#include <iostream>
#include <limits>
#include <optional>
#include <set>
#include <unordered_map>
using namespace std;
typedef unordered_map<string, double> CostGraph;
typedef unordered_map<string, optional<string>> ParentGraph;
typedef unordered_map<string, unordered_map<string, double>> WeightedGraph;
auto find_lowest_cost_node(CostGraph costs, const set<string>& processed) {
 auto lowest_cost = numeric_limits<double>::max();
 optional<string> lowest_cost_node = nullopt;
 for (const auto [node, cost] : costs) {
 if (cost < lowest_cost && find(processed.begin(), processed.end(), node) == processed.end()) {
 lowest_cost = cost;
 lowest_cost_node = node;
 }
 }
 return lowest_cost_node;
}
int main() {
 WeightedGraph graph;
 graph["start"] = {};
 graph["start"]["a"] = 6;
 graph["start"]["b"] = 2;
 graph["a"] = {};
 graph["a"]["fin"] = 1;
 graph["b"] = {};
 graph["b"]["a"] = 3;
 graph["b"]["fin"] = 5;
 graph["fin"] = {};
 CostGraph costs;
 costs["a"] = 6;
 costs["b"] = 2;
 costs["fin"] = numeric_limits<double>::max();
 ParentGraph parents;
 parents["a"] = "start";
 parents["b"] = "start";
 parents["fin"] = {};
 auto processed = set<string>{};
 while (const auto node = find_lowest_cost_node(costs, processed)) {
 const auto cost = costs[node.value()];
 const auto neighbours = graph[node.value()];
 for (const auto [n, c] : neighbours) {
 const auto new_cost = cost + c;
 if (costs[n] > new_cost) {
 costs[n] = new_cost;
 parents[n] = node;
 }
 }
 processed.insert(node.value());
 }
 cout << "Costs\n";
 for (const auto [k, v] : costs) {
 cout << k << ": " << v << "\n";
 }
 cout << "Parents\n";
 for (const auto [k, v] : parents) {
 if (v) {
 cout << k << ": " << v.value() << "\n";
 } else {
 cout << k << ": None\n";
 }
 }
}

• Emma X: Small comment to get you started: Don't use using namespace std, and use using instead of typedef, e.g. using CostGraph = std::unordered_map<std::string, double>;
• Loki Astari: Literal translations of algorithms between languages is unwise. The standard idioms of the language will not be used correctly.
• Loki Astari: Here is a close translation: stackoverflow.com/a/3448361/14065

Answer 1

Avoid translating Pythonisms

Dijkstra's algorithm really exploits nested dictionaries and weak typing which I used as an excuse to try out std::optional.

No, Dijkstra's algorithm does not require nested dictionaries nor weak typing. Maybe the Python implementation you are translating used these things, but maybe just because it was convenient in Python.

I strongly advise you to try to write idiomatic C++ code, not idiomatic Python translated to C++. What is convenient in Python might not be the best fit for C++, especially not when it comes to performance. I recommend you try to implement Dijkstra's using a priority queue.

Furthermore, putting everything into main() is bad practice. It's better to organize your code into functions and classes as appropriate, and that's true even in Python.

Use of typedefs

It's always a good idea to give a name to things, including types, that you use in multiple places in your code. However, in this case I think it would be better to create a class WeightedGraph that contains all the information about a graph with weighted edges. Then you can add member functions to this graph to add and remove vertices and edges, and a member function get_shortest_path() that uses Dijkstra's to calculate the shortest path between two given vertices and returns the list of vertices.

Use of std::optional

While it's possible to use std::optional here to represent the parent of a vertex, it might not be necessary. If you represent vertices by their name, then an empty string for the name might be used as the equivalent of None. And a more idiomatic C++ implementation of this algorithm would probably store each vertex's parent vertex using a pointer, in which case the nullptr would be the equivalent of None.