dijkstra 2 Algorithm
Dijkstra's algorithm (or Dijkstra's Shortest path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. A widely used application of shortest path algorithm is network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and open Shortest path As a solution, he re-observed the algorithm known as Prim's minimal spanning tree algorithm (known earlier to Jarník, and also rediscovered by Prim).
He designed the shortest path algorithm and later implemented it for ARMAC for a slightly simplified transportation map of 64 city in the Netherlands (64, so that 6 bits would be sufficient to encode the city number).What is the shortest manner to travel from Rotterdam to Groningen, in general: from given city to given city.
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 minDist(mdist, vset, V):
minVal = float("inf")
minInd = -1
for i in range(V):
if (not vset[i]) and mdist[i] < minVal:
minInd = i
minVal = mdist[i]
return minInd
def Dijkstra(graph, V, src):
mdist = [float("inf") for i in range(V)]
vset = [False for i in range(V)]
mdist[src] = 0.0
for i in range(V - 1):
u = minDist(mdist, vset, V)
vset[u] = True
for v in range(V):
if (
(not vset[v])
and graph[u][v] != float("inf")
and mdist[u] + graph[u][v] < mdist[v]
):
mdist[v] = mdist[u] + graph[u][v]
printDist(mdist, V)
if __name__ == "__main__":
V = int(input("Enter number of vertices: ").strip())
E = int(input("Enter number of edges: ").strip())
graph = [[float("inf") for i in range(V)] for j in range(V)]
for i in range(V):
graph[i][i] = 0.0
for i in range(E):
print("\nEdge ", i + 1)
src = int(input("Enter source:").strip())
dst = int(input("Enter destination:").strip())
weight = float(input("Enter weight:").strip())
graph[src][dst] = weight
gsrc = int(input("\nEnter shortest path source:").strip())
Dijkstra(graph, V, gsrc)
