CODEWITHSUNDEEP
pythongraph-theorydijkstra
Timothy Su
Timothy Su

Reputation: 21

Dijkstra's path python

I'm using Dijkstra module to create some function for mapping path. I have already added all the paths into the list, but am struggling with printing the path locations for the function.

Here's the graph I'm using

Path Graph

For example:

>>>prev, dist = dijkstra(g, ‘A’) 
>>>print_path(prev, ‘A’, ‘D’) 
‘D-B-A’

Additionally, how can I to create a function to suggest the shortest path for the input?
Example:

>>> suggest = shortest(g, “A”, “D”)
>>> suggest
{'C','B',’E'}

Here is my code:

from dijkstra import *

nodes = {'A', 'B', 'C', 'D', 'E'}

edges = [('A', 'B', 3), ('B', 'A', 3), ('A', 'C', 5), ('C', 'A', 5), 
         ('A', 'E', 2), ('B', 'D', 2), ('D', 'C', 1), ('C', 'E', 2), 
         ('D', 'E', 4), ('E', 'D', 4)]

map1 = (nodes, edges)

src = 'A'
prev, dist = dijkstra(map1, src)
print('Dijkstra for sources = ', src, '\nprev: ', prev, '\nDistances: ', dist)


g = create_graph()
add_vertex(g, "A")
add_vertex(g, "B")
add_vertex(g, "C")
add_vertex(g, "D")
add_vertex(g, "E")

add_edge(g, 'A', 'B', 3)
add_edge(g, 'B', 'A', 3)
add_edge(g, 'A', 'C', 5)
add_edge(g, 'C', 'A', 5)
add_edge(g, 'A', 'E', 2)
add_edge(g, 'E', 'A', 2)
add_edge(g, 'B', 'D', 2)
add_edge(g, 'D', 'B', 2)
add_edge(g, 'D', 'C', 1)
add_edge(g, 'C', 'E', 2)
add_edge(g, 'E', 'C', 2)
add_edge(g, 'D', 'E', 4)
add_edge(g, 'E', 'D', 4)


def print_path(previous, source, dest):
   print('path from', source, 'to', dest, ':')

for node in map1[0]:
   print_path(prev, 'A', node)

Upvotes: 1

Views: 475

Answers (1)

Subodh Dhabalia
Subodh Dhabalia

Reputation: 15

First Enter degree of matrix then enter the numbers of the matrix such that it is an adjacency matrix then enter source and target

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

def graph(mat, n, s, t):
    G = nx.Graph()
    for i in range(0, n):
        for j in range(0, n):
            if (i < j):
                if (mat[i][j] != 0):
                    e = mat[i][j]
                    G.add_edge(f"{i}", f"{j}", weight = e)

    nx.draw(G, with_labels = True)
    print("Path is\t", nx.dijkstra_path(G, source = s, target = t))
    plt.show()

n = int(input("enter degree of matrix:  "))
a = list(map(int, input("enter numbers:  ").split()))
mat = np.array(a).reshape(n, n)
print(mat)
s = str(input("enter source:  "))
t = str(input("enter target:  "))
graph(mat, n, s, t)

Upvotes: 1

Related Questions