Dijkstra Example

This example demonstrates the Breadth-First Search (BFS) algorithm on a simple pygraphs.Graph. The BFS algorithm explores the vertices of a graph in layers, starting from a given source vertex and visiting all its neighbors before moving on to the next layer of vertices.

Define the graphs

Create a simple disconnected graph of 7 vertices

#     Disconnected and weighted graph with 7 vertices for Dijkstra example.
#     Distance from vertex 0 to vertex 4 is 4.8.
#
# And a directed graph of 7 vertices
#
# .. figure:: /_static/weighted_graph_directed.png
#     :align: center
#     :width: 50%

#     Directed graph with 7 vertices for Dijkstra example. Distance from vertex 2 to
#     vertex 0 is 2.7.

from pygraphs import Graph

graph = [
    [(1, 1.2), (2, 0.2)],
    [(0, 1.2), (2, 1.5)],
    [(0, 0.2), (1, 1.5), (3, 3.2)],
    [(2, 3.2), (4, 1.4)],
    [(3, 1.4)],
    [(6, 2.3)],
    [(5, 2.3)],
]
undirected_graph = Graph.from_adjacency(graph)
print(undirected_graph.is_directed())  # False

graph = graph = [
    [(1, 1.2), (2, 0.2)],
    [(0, 1.2), (2, 1.5)],
    [(1, 1.5), (3, 3.2)],
    [(2, 1.4), (4, 1.4)],
    [(3, 1.4)],
    [(6, 2.3)],
    [],
]
directed_graph = Graph.from_adjacency(graph)
print(directed_graph.is_directed())  # True

False
True

Dijkstra Examples

Dijkstra Distances

Computes shortest distances from a source vertex to all other vertices. Unreachable vertices have distance -1. (see also pygraphs.dijkstra_distances())

from pygraphs import dijkstra_distances

start_vertex = 0
distances = dijkstra_distances(undirected_graph, start_vertex)
print(distances)  # Expected [0.0, 1.2, 0.2, 3.4, 4.8, -1.0, -1.0]

start_vertex = 2
distances = dijkstra_distances(directed_graph, start_vertex)
print(distances)  # Expected [2.7, 1.5, 0.0, 3.2, 4.6, -1.0, -1.0]

[0.0, 1.2, 0.2, 3.4000000000000004, 4.800000000000001, -1.0, -1.0]
[2.7, 1.5, 0.0, 3.2, 4.6, -1.0, -1.0]

Dijkstra Shortest Path

Returns the minimum-cost path between a source and a target vertex. (see also pygraphs.dijkstra_shortest_path())

from pygraphs import dijkstra_shortest_path

start_vertex = 0
end_vertex = 4
shortest_path = dijkstra_shortest_path(undirected_graph, start_vertex, end_vertex)
print(shortest_path)  # Expected [0, 2, 3, 4]

start_vertex = 2
end_vertex = 0
shortest_path = dijkstra_shortest_path(directed_graph, start_vertex, end_vertex)
print(shortest_path)  # Expected [2, 1, 0]

[0, 2, 3, 4]
[2, 1, 0]

Dijkstra Shortest Distance

Returns the total minimum cost between two vertices. (see also pygraphs.dijkstra_shortest_distance())

from pygraphs import dijkstra_shortest_distance

start_vertex = 0
end_vertex = 4
distance = dijkstra_shortest_distance(undirected_graph, start_vertex, end_vertex)
print(distance)  # Expected 4.8

start_vertex = 2
end_vertex = 0
distance = dijkstra_shortest_distance(directed_graph, start_vertex, end_vertex)
print(distance)  # Expected 2.7

4.800000000000001
2.7

Dijkstra Matrix

Computes the all-pairs shortest path matrix using Dijkstra. (see also pygraphs.dijkstra_matrix())

from pygraphs import dijkstra_matrix

matrix = dijkstra_matrix(undirected_graph)
print(matrix)

# Expected output:
# adjacency_matrix (shape=(7x7)):
# [[ 0.0  1.2  0.2  3.4  4.8 -1.0 -1.0]
#  [ 1.2  0.0  1.4  4.6  6.0 -1.0 -1.0]
#  [ 0.2  1.4  0.0  3.2  4.6 -1.0 -1.0]
#  [ 3.4  4.6  3.2  0.0  1.4 -1.0 -1.0]
#  [ 4.8  6.0  4.6  1.4  0.0 -1.0 -1.0]
#  [-1.0 -1.0 -1.0 -1.0 -1.0  0.0  2.3]
#  [-1.0 -1.0 -1.0 -1.0 -1.0  2.3  0.0]]

matrix = dijkstra_matrix(directed_graph)
print(matrix)

# Expected output:
# adjacency_matrix (shape=(7x7)):
# [[ 0.0  1.2  0.2  3.4  4.8 -1.0 -1.0]
#  [ 1.2  0.0  1.4  4.6  6.0 -1.0 -1.0]
#  [ 0.2  1.4  0.0  3.2  4.6 -1.0 -1.0]
#  [ 1.6  2.8  1.4  0.0  1.4 -1.0 -1.0]
#  [ 3.0  4.2  2.8  1.4  0.0 -1.0 -1.0]
#  [-1.0 -1.0 -1.0 -1.0 -1.0  0.0  2.3]
#  [-1.0 -1.0 -1.0 -1.0 -1.0 -1.0  0.0]]

[[0.0, 1.2, 0.2, 3.4000000000000004, 4.800000000000001, -1.0, -1.0], [1.2, 0.0, 1.4, 4.6, 6.0, -1.0, -1.0], [0.2, 1.4, 0.0, 3.2, 4.6, -1.0, -1.0], [3.4000000000000004, 4.6000000000000005, 3.2, 0.0, 1.4, -1.0, -1.0], [4.8, 6.0, 4.6, 1.4, 0.0, -1.0, -1.0], [-1.0, -1.0, -1.0, -1.0, -1.0, 0.0, 2.3], [-1.0, -1.0, -1.0, -1.0, -1.0, 2.3, 0.0]]
[[0.0, 1.2, 0.2, 3.4000000000000004, 4.800000000000001, -1.0, -1.0], [1.2, 0.0, 1.4, 4.6, 6.0, -1.0, -1.0], [2.7, 1.5, 0.0, 3.2, 4.6, -1.0, -1.0], [4.1, 2.9, 1.4, 0.0, 1.4, -1.0, -1.0], [5.5, 4.3, 2.8, 1.4, 0.0, -1.0, -1.0], [-1.0, -1.0, -1.0, -1.0, -1.0, 0.0, 2.3], [-1.0, -1.0, -1.0, -1.0, -1.0, -1.0, 0.0]]

Dijkstra k-annulus

Returns nodes whose shortest path distance is between an inner and outer bound. (see also pygraphs.dijkstra_k_annulus())

from pygraphs import dijkstra_k_annulus

start_vertex = 0
inner_distance = 0.1
outer_distance = 4.0

neighborhood = dijkstra_k_annulus(
    undirected_graph, start_vertex, inner_distance, outer_distance
)
print(neighborhood)  # Expected [1, 2, 3]

[1, 2, 3]

Dijkstra k-disk

Returns all nodes within a given distance threshold. (see also pygraphs.dijkstra_k_disk())

from pygraphs import dijkstra_k_disk

start_vertex = 0
distance = 4.0

neighborhood = dijkstra_k_disk(undirected_graph, start_vertex, distance)
print(neighborhood)  # Expected [0, 1, 2, 3]

[0, 1, 2, 3]