Repository: keon/algorithms
Pull request #599 (2019-12-01 11:30:57)

[ADD] Create all_pairs_shortest_path.py
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [X] **If creating a new file :**
  - [x] added links to it in the README files ?
  - [x] included tests with it ?
  - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


lcw921: Added unit tests. Request you to check.
keon: plz resolve conflict
lcw921: Plz check it again. I resolve conflicts.

2019년 12월 9일 (월) 오후 5:59, Keon <notifications@github.com>님이 작성:

> plz resolve conflict
>
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/keon/algorithms/pull/599?email_source=notifications&email_token=AJKV3FP7Y2IDVHMDN4XCTETQXYCGRA5CNFSM4JTLGZI2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEGILLIQ#issuecomment-563131810>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AJKV3FKNYXKZ7GZMXT5EOFLQXYCGRANCNFSM4JTLGZIQ>
> .
>


Patch:
diff --git a/README.md b/README.md
index d3bc636..8ddcb7e 100644
--- 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
index 646db09..a155c77 100644
--- 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 *


Test patch:
diff --git a/algorithms/graph/all_pairs_shortest_path.py b/algorithms/graph/all_pairs_shortest_path.py
new file mode 100644
index 0000000..46f3b7c
--- /dev/null
+++ 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
\ No newline at end of file
diff --git a/tests/test_graph.py b/tests/test_graph.py
index 699136a..48c2bbb 100644
--- 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 @@ class TestDijkstra(unittest.TestCase):
            [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):