Search⌘ K
AI Features
Home
Courses
Designing Graphical Causal Bayesian Networks in Python

Solution: Find the Shortest Path in a Small Town

Understand how to construct directed weighted graphs and apply Dijkstra's algorithm to find the shortest path and its length between nodes. This lesson guides you step-by-step through initializing the graph, adding weighted edges, and computing the shortest path, enhancing your network analysis skills in Python.

We'll cover the following...

The solution to the exercise

To solve the problem, we complete the lines calling Dijkstra's algorithm:

Python 3.8
# Create the graph
G = nx.DiGraph()
G.add_weighted_edges_from([
    ('A', 'B', 5),
    ('A', 'C', 3),
    ('B', 'D', 2),
    ('C', 'D', 4),
    ('C', 'E', 6),
    ('D', 'E', 1),
    ('D', 'F', 3),
    ('E', 'G', 5),
    ('F', 'G', 2),
    ('G', 'H', 4),
    ('G', 'I', 7),
    ('H', 'I', 2),
    ('I', 'J', 1),
])
# Find the shortest path using Dijkstra's algorithm
shortest_path = nx.dijkstra_path(G, 'A', 'J')
shortest_path_length = nx.dijkstra_path_length(G, 'A', 'J')
print(f"Shortest path: {' -> '.join(shortest_path)}")
print(f"Total distance: {shortest_path_length}")
def test(N=[]):
    return shortest_path

  • Line 2: We ...