Before we delve into implementing Dijkstra’s Algorithm, we need a graph to explore it, but how exactly do we represent graphs in python? One of the ways to represent graph is through an adjacency list using a Python dictionary.
Take a look at the following graph represented by an adjacency list:
graph = { 'A': [('B', 10), ('C', 3)], 'B': [('C', 3), ('D', 2)], 'C': [('D', 2)], 'D': [('E', 10)], 'E': [('B', 15)], }
Reading this adjacency list, we can tell the graph
has 5 vertices: 'A', 'B', 'C', 'D', 'E'
.
There is a path from 'A'
to 'B'
with a cost (or edge weight) of 10
and a path from 'A'
to 'C'
with a cost of 3
.
There is a path from 'B'
to 'C'
with a cost of 3
and a path from 'B'
to 'D'
with a cost of 2.
There is a path from 'C'
to 'D'
with a cost of 2
.
There is a path from 'D'
to 'E'
with a cost of 10
.
There is a path from 'E'
to 'B'
with a cost of 15
.
Instructions
Run the code to see the different vertices and edges of the graph. Try adding and removing edges and see how it effects the graph!