fork download
copy 
  1. # Implementation of Johnson's algorithm in Python3 
  2.  
  3. # Import function to initialize the dictionary 
  4. from collections import defaultdict 
  5. MAX_INT = float('Inf') 
  6.  
  7. # Returns the vertex with minimum 
  8. # distance from the source 
  9. def minDistance(dist, visited): 
  10.  
  11. 	(minimum, minVertex) = (MAX_INT, 0) 
  12. 	for vertex in range(len(dist)): 
  13. 		if minimum > dist[vertex] and visited[vertex] == False: 
  14. 			(minimum, minVertex) = (dist[vertex], vertex) 
  15.  
  16. 	return minVertex 
  17.  
  18.  
  19. # Dijkstra Algorithm for Modified 
  20. # Graph (removing negative weights) 
  21. def Dijkstra(graph, modifiedGraph, src): 
  22.  
  23. 	# Number of vertices in the graph 
  24. 	num_vertices = len(graph) 
  25.  
  26. 	# Dictionary to check if given vertex is 
  27. 	# already included in the shortest path tree 
  28. 	sptSet = defaultdict(lambda : False) 
  29.  
  30. 	# Shortest distance of all vertices from the source 
  31. 	dist = [MAX_INT] * num_vertices 
  32.  
  33. 	dist[src] = 0
  34.  
  35. 	for count in range(num_vertices): 
  36.  
  37. 		# The current vertex which is at min Distance 
  38. 		# from the source and not yet included in the 
  39. 		# shortest path tree 
  40. 		curVertex = minDistance(dist, sptSet) 
  41. 		sptSet[curVertex] = True
  42.  
  43. 		for vertex in range(num_vertices): 
  44. 			if ((sptSet[vertex] == False) and
  45. 				(dist[vertex] > (dist[curVertex] +
  46. 				modifiedGraph[curVertex][vertex])) and
  47. 				(graph[curVertex][vertex] != 0)): 
  48.  
  49. 				dist[vertex] = (dist[curVertex] +
  50. 								modifiedGraph[curVertex][vertex]); 
  51.  
  52. 	# Print the Shortest distance from the source 
  53. 	# for vertex in range(num_vertices): 
  54. 		# print ('Vertex ' + str(vertex) + ': ' + str(dist[vertex])) 
  55.  
  56. # Function to calculate shortest distances from source 
  57. # to all other vertices using Bellman-Ford algorithm 
  58. def BellmanFord(edges, graph, num_vertices): 
  59.  
  60. 	# Add a source s and calculate its min 
  61. 	# distance from every other node 
  62. 	dist = [MAX_INT] * (num_vertices + 1) 
  63. 	dist[num_vertices] = 0
  64. 	#yes
  65.  
  66. 	for i in range(num_vertices): 
  67. 		edges.append([num_vertices, i, 0]) 
  68.  
  69. 	for i in range(num_vertices): 
  70. 		for (src, des, weight) in edges: 
  71. 			if((dist[src] != MAX_INT) and (dist[src] + weight < dist[des])): 
  72. 				dist[des] = dist[src] + weight 
  73. 	# Don't send the value for the source added 
  74. 	print(dist[0:num_vertices])
  75. 	return dist[0:num_vertices] 
  76.  
  77. # Function to implement Johnson Algorithm 
  78. def JohnsonAlgorithm(graph): 
  79.  
  80. 	edges = [] 
  81.  
  82. 	# Create a list of edges for Bellman-Ford Algorithm 
  83. 	for i in range(len(graph)): 
  84. 		for j in range(len(graph[i])): 
  85.  
  86. 			if graph[i][j] != 0: 
  87. 				edges.append([i, j, graph[i][j]]) 
  88.  
  89. 	# Weights used to modify the original weights 
  90. 	modifyWeights = BellmanFord(edges, graph, len(graph)) 
  91.  
  92. 	modifiedGraph = [[0 for x in range(len(graph))] for y in
  93. 					range(len(graph))] 
  94. 	# Modify the weights to get rid of negative weights 
  95. 	for i in range(len(graph)): 
  96. 		for j in range(len(graph[i])): 
  97.  
  98. 			if graph[i][j] != 0: 
  99. 				modifiedGraph[i][j] = (graph[i][j] +
  100. 						modifyWeights[i] - modifyWeights[j]); 
  101.  
  102. 	# print ('Modified Graph: ' + str(modifiedGraph)) 
  103.  
  104. 	# Run Dijkstra for every vertex as source one by one 
  105. 	for src in range(len(graph)): 
  106. 		# print ('\nShortest Distance with vertex ' +
  107. 		# 				str(src) + ' as the source:\n') 
  108. 		Dijkstra(graph, modifiedGraph, src) 
  109.  
  110. # Driver Code 
  111. graph = [[0, -5, 2, 3], 
  112. 		[0, 0, 4, 0], 
  113. 		[0, 0, 0, 1], 
  114. 		[0, 0, 0, 0]] 
  115.  
  116. JohnsonAlgorithm(graph) 
  117.  
Success #stdin #stdout 0.01s 27712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0, -5, -1, 0]
https://ideone.com/4Eg835
language:
Python 3 (python  3.9.5)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!