Shortest Paths

This example demonstrates how to find the shortest distance between two vertices of a weighted or an unweighted graph.

import igraph as ig
import matplotlib.pyplot as plt

To find the shortest path or distance between two nodes, we can use igraph.GraphBase.get_shortest_paths(). If we’re only interested in counting the unweighted distance, then we can do the following:

g = ig.Graph(
    [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
results = g.get_shortest_paths(1, to=4, output="vpath")

# results = [[1, 0, 2, 4]]

We can print the result of the computation:

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)
    print("End node could not be reached!")
Shortest distance is:  3

If the edges have weights, things are a little different. First, let’s add weights to our graph edges:["weight"] = [2, 1, 5, 4, 7, 3, 2]

To get the shortest paths on a weighted graph, we pass the weights as an argument. For a change, we choose the output format as "epath" to receive the path as an edge list, which can be used to calculate the length of the path.

results = g.get_shortest_paths(0, to=5,["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 +=[e]["weight"]
    print("Shortest weighted distance is: ", distance)
    print("End node could not be reached!")
Shortest weighted distance is:  8


In case you are wondering how the visualization figure was done, here’s the code:['width'] = 0.5[results[0]]['width'] = 2.5

fig, ax = plt.subplots()
shortest path visualisation

Total running time of the script: (0 minutes 0.213 seconds)

Gallery generated by Sphinx-Gallery