[ADD] Create all_pairs_shortest_path.py (keon#599)

lcw921 · keon · commit b45667021cb1 · 2019-12-10T20:27:23.000-08:00
* [ADD] Create all_pairs_shortest_path.py

* [FIX]Update example and Fix Code

* [FIX] Edit explanation.

* Update README.md

* Add unittest
diff --git a/README.md b/README.md
@@ -160,6 +160,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [satisfiability](algorithms/graph/satisfiability.py)
     - [tarjan](algorithms/graph/tarjan.py)
     - [traversal](algorithms/graph/traversal.py)
+    - [all_pairs_shortest_path](algorithms/graph/all_pairs_shortest_path.py)
     - [bellman_ford](algorithms/graph/bellman_ford.py)
 - [heap](algorithms/heap)
     - [merge_sorted_k_lists](algorithms/heap/merge_sorted_k_lists.py)
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
@@ -1,3 +1,4 @@
 from .tarjan import *
 from .check_bipartite import *
+from .all_pairs_shortest_path import *
 from .bellman_ford import *
diff --git a/algorithms/graph/all_pairs_shortest_path.py b/algorithms/graph/all_pairs_shortest_path.py
@@ -0,0 +1,28 @@
+"""
+Given a n*n adjacency array.
+it will give you all pairs shortest path length.
+use deepcopy to preserve the original information.
+
+Time complexity : O(E^3)
+
+example
+
+a = [[0, 0.1, 0.101, 0.142, 0.277], [0.465, 0, 0.191, 0.192, 0.587], [0.245, 0.554, 0, 0.333, 0.931], [1.032, 0.668, 0.656, 0, 0.151], [0.867, 0.119, 0.352, 0.398, 0]]
+
+result 
+
+[[0, 0.1, 0.101, 0.142, 0.277], [0.436, 0, 0.191, 0.192, 0.34299999999999997], [0.245, 0.345, 0, 0.333, 0.484], [0.706, 0.27, 0.46099999999999997, 0, 0.151], [0.5549999999999999, 0.119, 0.31, 0.311, 0]]
+
+"""
+import copy
+
+def all_pairs_shortest_path(adjacency_matrix):
+    new_array = copy.deepcopy(adjacency_matrix)
+
+    for k in range(len(new_array)):
+        for i in range(len(new_array)):
+            for j in range(len(new_array)):
+                if new_array[i][j] > new_array[i][k] + new_array[k][j]:
+                    new_array[i][j] = new_array[i][k] + new_array[k][j]           
+    
+    return new_array
diff --git a/tests/test_graph.py b/tests/test_graph.py
@@ -1,6 +1,7 @@
 from algorithms.graph import Tarjan
 from algorithms.graph import check_bipartite
 from algorithms.graph.dijkstra import Dijkstra
+from algorithms.graph import all_pairs_shortest_path
 from algorithms.graph import bellman_ford
 
 import unittest
@@ -75,7 +76,19 @@ def test_dijkstra(self):
            [0, 0, 2, 0, 0, 0, 6, 7, 0] 
           ]; 
 
-        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14]);
+        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14])
+
+class TestAll_Pairs_Shortest_Path(unittest.TestCase):
+    
+    def test_all_pairs_shortest_path(self):
+        graph = [[0, 0.1, 0.101, 0.142, 0.277], 
+                 [0.465, 0, 0.191, 0.192, 0.587], 
+                 [0.245, 0.554, 0, 0.333, 0.931], 
+                 [1.032, 0.668, 0.656, 0, 0.151], 
+                 [0.867, 0.119, 0.352, 0.398, 0]]
+        result = all_pairs_shortest_path(graph)
+
+        self.assertEqual(result, [[0, 0.1, 0.101, 0.142, 0.277], [0.436, 0, 0.191, 0.192, 0.34299999999999997], [0.245, 0.345, 0, 0.333, 0.484], [0.706, 0.27, 0.46099999999999997, 0, 0.151], [0.5549999999999999, 0.119, 0.31, 0.311, 0]])
         
 class TestBellmanFord(unittest.TestCase):
     def test_bellman_ford(self):
