Learn

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!

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?