graph algorithms

diyajaiswal11 · diyajaiswal11 · commit 1da2bfd8db39 · 2020-10-01T00:37:06.000+05:30
diff --git a/python/graph_algorithms/dijkstra_shortest_path.py b/python/graph_algorithms/dijkstra_shortest_path.py
@@ -0,0 +1,41 @@
+import sys
+def to_be_visited():
+  global visited_and_distance
+  v = -10
+  for index in range(number_of_vertices):
+    if visited_and_distance[index][0] == 0 \
+      and (v < 0 or visited_and_distance[index][1] <= \
+      visited_and_distance[v][1]):
+        v = index
+  return v
+vertices = [[0, 1, 1, 0],
+            [0, 0, 1, 0],
+            [0, 0, 0, 1],
+            [0, 0, 0, 0]]
+edges =  [[0, 3, 4, 0],
+          [0, 0, 0.5, 0],
+          [0, 0, 0, 1],
+          [0, 0, 0, 0]]
+
+number_of_vertices = len(vertices[0])
+visited_and_distance = [[0, 0]]
+for i in range(number_of_vertices-1):
+  visited_and_distance.append([0, sys.maxsize])
+
+for vertex in range(number_of_vertices):
+  to_visit = to_be_visited()
+  for neighbor_index in range(number_of_vertices):
+    if vertices[to_visit][neighbor_index] == 1 and \
+     visited_and_distance[neighbor_index][0] == 0:
+      new_distance = visited_and_distance[to_visit][1] \
+      + edges[to_visit][neighbor_index]
+      if visited_and_distance[neighbor_index][1] > new_distance:
+        visited_and_distance[neighbor_index][1] = new_distance
+  visited_and_distance[to_visit][0] = 1
+
+i = 0 
+    
+for distance in visited_and_distance:
+  print("The shortest distance of ",chr(ord('a') + i),\
+  " from the source vertex a is:",distance[1])
+  i = i + 1
diff --git a/python/graph_algorithms/floyd_warshall.py b/python/graph_algorithms/floyd_warshall.py
@@ -0,0 +1,31 @@
+
+nV = 4
+
+INF = 999
+
+def floyd_warshall(G):
+    distance = list(map(lambda i: list(map(lambda j: j, i)), G))
+    for k in range(nV):
+        for i in range(nV):
+            for j in range(nV):
+                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
+    print_solution(distance)
+
+def print_solution(distance):
+    for i in range(nV):
+        for j in range(nV):
+            if(distance[i][j] == INF):
+                print("INF", end=" ")
+            else:
+                print(distance[i][j], end="  ")
+        print(" ")
+
+
+G = [[0, 3, INF, 5],
+         [2, 0, INF, 4],
+         [INF, 1, 0, INF],
+         [INF, INF, 2, 0]]
+floyd_warshall(G)
+Floyd Warshall Algorithm Complexity
+Time Complexity
+There are three lo
