FilesExpand file tree

 Write-for-current-Python

/

dijkstra_2.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (45 loc) · 1.5 KB

 Write-for-current-Python

/

dijkstra_2.py

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (45 loc) · 1.5 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

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)