Shortest Paths ¶
Shortest Paths¶
This example demonstrates how to find the shortest distance between two vertices on a weighted and unweighted graph.
To find the shortest path or distance between two nodes, we can use get_shortest_paths()
. If we’re only interested in counting the unweighted distance, then we can do the following:
import igraph as ig
import matplotlib.pyplot as plt
# Find the shortest path on an unweighted graph
g = ig.Graph(
6,
[(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
)
# g.get_shortest_paths() returns a list of vertex ID paths
results = g.get_shortest_paths(1, to=4, output="vpath") # results = [[1, 0, 2, 4]]
if len(results[0]) > 0:
# The distance is the number of vertices in the shortest path minus one.
print("Shortest distance is: ", len(results[0])-1)
else:
print("End node could not be reached!")
If the edges have weights, we pass them in as an argument. Note that we specify the output format as "epath"
, in order to receive the path as an edge list. This is used to calculate the length of the path.
# Find the shortest path on a weighted graph
g.es["weight"] = [2, 1, 5, 4, 7, 3, 2]
# g.get_shortest_paths() returns a list of edge ID paths
results = g.get_shortest_paths(
0,
to=5,
weights=g.es["weight"],
output="epath",
)
# results = [[1, 3, 5]]
if len(results[0]) > 0:
# Add up the weights across all edges on the shortest path
distance = 0
for e in results[0]:
distance += g.es[e]["weight"]
print("Shortest weighted distance is: ", distance)
else:
print("End node could not be reached!")
The output of these these two shortest paths are:
Shortest distance is: 3
Shortest weighted distance is: 8

The graph g with the shortest path from vertex 0 to vertex 5 highlighted.¶
Note
get_shortest_paths()
returns a list of lists becuase the to argument can also accept a list of vertex IDs. In that case, the shortest path to all each vertex is found and stored in the results array.If you’re interested in finding all shortest paths, take a look at
get_all_shortest_paths()
.
In case you are wondering how the visualization figure was done, here’s the code:
import igraph as ig
import matplotlib.pyplot as plt
# Construct the graph
g = ig.Graph(
6,
[(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
)
g.es["weight"] = [2, 1, 5, 4, 7, 3, 2]
# Get a shortest path along edges
results = g.get_shortest_paths(
0,
to=5,
weights=g.es["weight"],
output="epath",
)
# results = [[1, 3, 5]]
# Plot graph
g.es['width'] = 0.5
g.es[results[0]]['width'] = 2.5
fig, ax = plt.subplots()
ig.plot(
g,
target=ax,
layout='circle',
vertex_color='steelblue',
vertex_label=range(g.vcount()),
edge_width=g.es['width'],
edge_label=g.es["weight"],
edge_color='#666',
edge_align_label=True,
edge_background='white'
)