Comparator for Dijkstra's and Ford-Bellman's pathfinding algorithms

graph.txt

0 2
- 1 - 2 -
- - 2 - 3
- - - 5 -
- 4 - - 3
- - 1 - -

ShortestWay.py

# ShortestWay - comparator for Dijkstra's and Ford-Bellman's pathfinding algorithms
# Requires `graph.txt` - start and end points and an adjacency matrix that defines the graph
# Put dashes (-) where there's no way

import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import networkx as nx
from queue import PriorityQueue

inf = float('inf')

with open('graph.txt') as file:
    s, f = map(int, file.readline().split())
    g = [[inf if i == '-' else int(i) for i in line.split()] for line in file]


def matrix_to_graph(matrix):
    graph = nx.DiGraph()
    for i, row in enumerate(matrix):
        for j, cell in enumerate(row):
            if cell != inf:
                graph.add_edge(i, j, weight=cell)
    return graph


def path_to_edges(path):
    edges = []
    for i in range(1, len(path)):
        edges.append((path[i - 1], path[i]))
    return edges


def modify(q, v, d):
    nq = PriorityQueue()
    while not q.empty():
        dist_i, i = q.get()
        if i != v:
            nq.put((dist_i, i))
        else:
            nq.put((d, v))
    return nq


def dijkstra(g, s, f):
    dist = [inf] * len(g)
    dist[s] = 0
    prev = [None] * len(g)

    q = PriorityQueue()
    verts = set(range(len(g)))
    q.put((dist[s], s))
    verts.remove(s)

    for i in verts:
        q.put((dist[i], i))

    while not q.empty():
        dist_u, u = q.get()
        for i in range(len(g)):
            if g[u][i] != inf:
                if dist[i] > dist_u + g[u][i]:
                    dist[i] = dist_u + g[u][i]
                    q = modify(q, i, dist[i])
                    prev[i] = u

    path = []
    while f is not None:
        path.insert(0, f)
        f = prev[f]

    return path


def ford_bellman(g, s, f):
    n = len(g)
    dist = [inf] * n
    dist[s] = 0
    prev = [None] * n

    for itr in range(n - 1):
        for i in range(n):
            for j in range(n):
                if g[i][j] != inf and dist[j] > dist[i] + g[i][j]:
                    dist[j] = dist[i] + g[i][j]
                    prev[j] = i

    path = []
    while f is not None:
        path.insert(0, f)
        f = prev[f]

    return path


all_verts = set(range(len(g)))
di_path = dijkstra(g, s, f)
fb_path = ford_bellman(g, s, f)

di_edges = set(path_to_edges(di_path))
fb_edges = set(path_to_edges(fb_path))

G = matrix_to_graph(g)
pos = nx.circular_layout(G)

nodes = nx.draw_networkx_nodes(G, pos,
                               node_color='snow')
nodes.set_edgecolor('black')
nx.draw_networkx_labels(G, pos, {i: str(i) for i in all_verts}, font_size=10)

nx.draw_networkx_edges(G, pos)
nx.draw_networkx_edges(G, pos, edgelist=di_edges,
                       edge_color='lightblue')
nx.draw_networkx_edges(G, pos, edgelist=fb_edges,
                       edge_color='lightcoral')
nx.draw_networkx_edges(G, pos, edgelist=di_edges & fb_edges,
                       edge_color='plum')
nx.draw_networkx_edge_labels(G, pos,
                             edge_labels=nx.get_edge_attributes(G, 'weight'))

blue = mpatches.Patch(color='lightblue',
                      label='Path using the Dijkstra\'s algorithm')
red = mpatches.Patch(color='lightcoral',
                     label='Path using the Ford-Bellman\'s algorithm')
purp = mpatches.Patch(color='plum',
                      label='Matching edges')

plt.legend(handles=[blue, red, purp],
           bbox_transform=plt.gcf().transFigure,
           bbox_to_anchor=(1, 1))

plt.axis('off')
fig = plt.gcf()
fig.canvas.set_window_title('Search for the shortest way')
plt.show()