Shortest Path Analysis in NetworkX

Shortest path analysis is one of the most common graph tasks. It helps answer questions like how to route between locations, how many steps separate two entities, or which path minimizes total cost. NetworkX makes it straightforward to compute shortest paths for both unweighted and weighted graphs.

This tutorial shows how to build a graph, compare weighted and unweighted shortest paths, calculate path lengths, and visualize the selected route.

### Basic Shortest Path in an Unweighted Graph

Let's start with a simple graph where every edge has equal cost.

import networkx as nx

G = nx.Graph()
G.add_edges_from(
    [
        ("A", "B"),
        ("A", "C"),
        ("B", "D"),
        ("C", "D"),
        ("D", "E"),
        ("C", "F"),
        ("F", "E"),
    ]
)

path = nx.shortest_path(G, "A", "E")
path_length = nx.shortest_path_length(G, "A", "E")

print("Shortest path:", " -> ".join(path))
print("Path length:", path_length)

Shortest path: A -> B -> D -> E
Path length: 3

- In an unweighted graph, NetworkX minimizes the number of edges.
- **`nx.shortest_path`** returns the route itself, while **`nx.shortest_path_length`** returns the number of steps.

### Shortest Path in a Weighted Graph

When edges have costs such as distance or travel time, you can tell NetworkX to optimize for weight instead of hop count.

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from(
    [
        ("A", "B", 2),
        ("A", "C", 5),
        ("B", "D", 2),
        ("C", "D", 1),
        ("D", "E", 3),
        ("C", "F", 2),
        ("F", "E", 1),
    ]
)

path = nx.shortest_path(G, "A", "E", weight="weight")
distance = nx.shortest_path_length(G, "A", "E", weight="weight")

print("Weighted shortest path:", " -> ".join(path))
print("Total weight:", distance)

Weighted shortest path: A -> B -> D -> E
Total weight: 7

- **`weight="weight"`** tells NetworkX to use the edge weights when comparing routes.
- The best path in a weighted graph may be different from the best path in an unweighted graph.

### Comparing Weighted and Unweighted Results

It is useful to compare both interpretations because “fewest stops” and “lowest cost” are not always the same thing.

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from(
    [
        ("A", "B", 1),
        ("B", "E", 10),
        ("A", "C", 3),
        ("C", "D", 2),
        ("D", "E", 2),
    ]
)

unweighted_path = nx.shortest_path(G, "A", "E")
weighted_path = nx.shortest_path(G, "A", "E", weight="weight")

print("Unweighted shortest path:", " -> ".join(unweighted_path))
print("Weighted shortest path:", " -> ".join(weighted_path))
print("Weighted distance:", nx.shortest_path_length(G, "A", "E", weight="weight"))

Unweighted shortest path: A -> B -> E
Weighted shortest path: A -> C -> D -> E
Weighted distance: 7

- The unweighted version minimizes the number of edges.
- The weighted version minimizes total edge cost.

### Visualizing the Graph and Highlighting the Path

A graph diagram makes it easier to inspect the chosen route and understand why it was selected.

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_weighted_edges_from(
    [
        ("A", "B", 2),
        ("A", "C", 5),
        ("B", "D", 2),
        ("C", "D", 1),
        ("D", "E", 3),
        ("C", "F", 2),
        ("F", "E", 1),
    ]
)

path = nx.shortest_path(G, "A", "E", weight="weight")
path_edges = list(zip(path, path[1:]))

pos = nx.spring_layout(G, seed=42)

plt.figure(figsize=(9, 6))
nx.draw(
    G,
    pos,
    with_labels=True,
    node_color="lightblue",
    node_size=900,
    edge_color="gray",
    font_size=11,
)
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color="red", width=3)
nx.draw_networkx_edge_labels(G, pos, edge_labels=nx.get_edge_attributes(G, "weight"))

plt.title("Weighted Graph with Highlighted Shortest Path")
plt.axis("off")
plt.show()

- The red edges show the selected shortest route.
- Edge labels make it easy to verify why one route is cheaper than another.

### Practical Example: Transport Network

Here is a more realistic example where nodes represent cities and edge weights represent travel distance.

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_weighted_edges_from(
    [
        ("New York", "Chicago", 790),
        ("New York", "Atlanta", 870),
        ("Chicago", "Denver", 1000),
        ("Atlanta", "Dallas", 780),
        ("Dallas", "Denver", 780),
        ("Denver", "Los Angeles", 1015),
        ("Dallas", "Los Angeles", 1435),
        ("Atlanta", "Houston", 790),
        ("Houston", "Los Angeles", 1545),
    ]
)

start = "New York"
end = "Los Angeles"

path = nx.shortest_path(G, start, end, weight="weight")
distance = nx.shortest_path_length(G, start, end, weight="weight")

print(f"Shortest route from {start} to {end}:")
print(" -> ".join(path))
print(f"Total distance: {distance}")

path_edges = list(zip(path, path[1:]))
pos = nx.spring_layout(G, seed=21)

plt.figure(figsize=(11, 7))
nx.draw(
    G,
    pos,
    with_labels=True,
    node_color="#D9F0A3",
    node_size=1200,
    edge_color="#BBBBBB",
    font_size=10,
)
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color="crimson", width=3)
nx.draw_networkx_edge_labels(G, pos, edge_labels=nx.get_edge_attributes(G, "weight"), font_size=8)

plt.title("Transport Network with Shortest Route Highlighted")
plt.axis("off")
plt.show()

Shortest route from New York to Los Angeles:
New York -> Chicago -> Denver -> Los Angeles
Total distance: 2805

- This example models the kind of problem shortest path algorithms are often used for in routing and logistics.
- The highlighted route shows the minimum total travel distance based on the weights you provided.

### Conclusion

NetworkX makes shortest path analysis easy for both simple and weighted graphs. By combining path computation with a clear visualization, you can inspect not just the answer, but also the network structure that produced it.

Shortest Path Analysis in NetworkX

You may also like