shortest_path.py

# Dijkstra - Single Source Shortest Path- does not work for negetive edge weights- greedy algo
# Bellman Ford - Single source shortest path - valid for negetive edge weights
# Floyd Warshall - All pair shortest path
#       0,    1,    2,  3,    4,     5
#   0    0,   2,    4,  -1,  -1,    -1
#   1   -1,   0,    1,   4,   2,    -1
#   2   -1,  -1,    0,  -1,   3,    -1
#   3   -1,  -1,    -1,  0,  -1,     2
#   4   -1,  -1,    -1,  3,  -1,     2
#   5  - 1,  -1,    -1, -1,  -1,     0
# [[0, 2, 3, 6, 4, -1],
# [-1, 0, 1, 4, 2, -1],
# [-1, -1, 0, 6, 3, 5],
# [-1, -1, -1, 0, -1, 2],
# [-1, -1, -1, 3, -1, 2],
# [-1, -1, -1, -1, -1, 0]]
col = 6
arr = [[0, 2, 4, 100, 100, 100],
       [100, 0, 1, 4, 2, 100],
       [100, 100, 0, 100, 3, 100],
       [100, 100, 100, 0, 100, 2],
       [100, 100, 100, 3, 100, 2],
       [100, 100, 100, 100, 100, 0]]
def update_shortest_path_via_neighbour(vertex, neighbour):
    for j in range(0, col):
        if arr[vertex][j] > arr[vertex][neighbour] + arr[neighbour][j]:
            arr[vertex][j] = arr[vertex][neighbour] + arr[neighbour][j]
def find_nearest(vertex):
    min = 1000
    pos = 0
    for j in range(0, col):
        if min > arr[vertex][j] and vertex is not j:
            min = arr[vertex][j]
            pos = j
    return pos
def shortest_path_per_vertex(v):
    vertex_list = [i for i in range(0, 6) if i != v]
    visited_vertices = [v]
    i = 0
    while vertex_list != []:
        print("vertex_list", vertex_list)
        print("visited_vertices", visited_vertices)
        nearest_neighbour = find_nearest(visited_vertices[i])
        print("nearest_neighbour", nearest_neighbour)
        visited_vertices.append(nearest_neighbour)
        update_shortest_path_via_neighbour(v, nearest_neighbour)
        i += 1
        if nearest_neighbour not in vertex_list:
            vertex_list.remove(vertex_list[0])
        else:
            vertex_list.remove(nearest_neighbour)
for v in range(0, 6):
    shortest_path_per_vertex(v)
print(arr)