Python/graphs/bellman_ford.py at master · wcfylcf/Python · GitHub

History

54 lines (41 loc) · 1.22 KB

Raw

from __future__ import print_function

def printDist(dist, V):

print("\nVertex Distance")

for i in range(V):

if dist[i] != float('inf') :

print(i,"\t",int(dist[i]),end = "\t")

else:

print(i,"\t","INF",end="\t")

print()

def BellmanFord(graph, V, E, src):

mdist=[float('inf') for i in range(V)]

mdist[src] = 0.0

for i in range(V-1):

for j in range(V):

u = graph[j]["src"]

v = graph[j]["dst"]

w = graph[j]["weight"]

if mdist[u] != float('inf') and mdist[u] + w < mdist[v]:

mdist[v] = mdist[u] + w

for j in range(V):

u = graph[j]["src"]

v = graph[j]["dst"]

w = graph[j]["weight"]

if mdist[u] != float('inf') and mdist[u] + w < mdist[v]:

print("Negative cycle found. Solution not possible.")

return

printDist(mdist, V)

#MAIN

V = int(input("Enter number of vertices: "))

E = int(input("Enter number of edges: "))

graph = [dict() for j in range(E)]

for i in range(V):

graph[i][i] = 0.0

for i in range(E):

print("\nEdge ",i+1)

src = int(input("Enter source:"))

dst = int(input("Enter destination:"))

weight = float(input("Enter weight:"))

graph[i] = {"src": src,"dst": dst, "weight": weight}

gsrc = int(input("\nEnter shortest path source:"))

BellmanFord(graph, V, E, gsrc)

Python/graphs/bellman_ford.py at master · wcfylcf/Python · GitHub

Expand file tree

Breadcrumbs

bellman_ford.py

Latest commit

History

Breadcrumbs

bellman_ford.py

File metadata and controls