Posts tagged with “graphs”

July 29, 2016

Dijkstra's Algorithm in Python 3

Greed is good. And Dijkstra’s algorithm is greedy. Dijkstra’s algorithm not only calculates the shortest (lowest weight) path on a graph from source vertex S to destination V, but also calculates the shortest path from S to every other vertex. My implementation in Python doesn’t…

July 26, 2016

Graphs and Dynamic Programming

I’ve been learning graphs and dynamic programming somewhat interleaved. Dynamic programming tends to help solve graph problems because: Every problem solvable by dynamic programming can be represented in a DAG. A couple of things I discovered in my experiments: Using a queue for graph…