Add bellman-ford algorithm (keon#601)

ahnhyunjun417 · keon · commit c6d4b7340d8e · 2019-12-09T00:53:08.000-08:00
* fix the comment on line 33 (left-&gt;right)

* [Add] bellman-ford algorithm

* Update bellman_ford.py

* Update merge_sort.py

* Update README.md

* Update bellman_ford.py

* Update test_graph.py

* Update bellman_ford.py

* Update test_graph.py

* Update test_graph.py

* Update test_graph.py

* Update __init__.py

* Update test_graph.py

* Update bellman_ford.py

* Update test_graph.py
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)
+    - [bellman_ford](algorithms/graph/bellman_ford.py)
 - [heap](algorithms/heap)
     - [merge_sorted_k_lists](algorithms/heap/merge_sorted_k_lists.py)
     - [skyline](algorithms/heap/skyline.py)
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
@@ -1,2 +1,3 @@
 from .tarjan import *
 from .check_bipartite import *
+from .bellman_ford import *
diff --git a/algorithms/graph/bellman_ford.py b/algorithms/graph/bellman_ford.py
@@ -0,0 +1,44 @@
+'''
+This Bellman-Ford Code is for determination whether we can get
+shortest path from given graph or not for single-source shortest-paths problem.
+In other words, if given graph has any negative-weight cycle that is reachable
+from the source, then it will give answer False for "no solution exits".
+For argument graph, it should be a dictionary type
+such as
+graph = {
+    'a': {'b': 6, 'e': 7},
+    'b': {'c': 5, 'd': -4, 'e': 8},
+    'c': {'b': -2},
+    'd': {'a': 2, 'c': 7},
+    'e': {'b': -3}
+}
+'''
+
+def bellman_ford(graph, source):
+    weight = {}
+    pre_node = {}
+
+    initialize_single_source(graph, source, weight, pre_node)
+
+    for i in range(1, len(graph)):
+        for node in graph:
+            for adjacent in graph[node]:
+                if weight[adjacent] > weight[node] + graph[node][adjacent]:
+                    weight[adjacent] = weight[node] + graph[node][adjacent]
+                    pre_node[adjacent] = node
+
+    for node in graph:
+        for adjacent in graph[node]:
+            if weight[adjacent] > weight[node] + graph[node][adjacent]:
+                return False
+
+    return True
+
+def initialize_single_source(graph, source, weight, pre_node):
+
+    for node in graph:
+        weight[node] = float('inf')
+        pre_node[node] = None
+
+    weight[source] = 0
+    
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 bellman_ford
 
 import unittest
 
@@ -74,4 +75,26 @@ 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 TestBellmanFord(unittest.TestCase):
+    def test_bellman_ford(self):
+        graph1 = {
+            'a': {'b': 6, 'e': 7},
+            'b': {'c': 5, 'd': -4, 'e': 8},
+            'c': {'b': -2},
+            'd': {'a': 2, 'c': 7},
+            'e': {'b': -3}
+        }
+    
+        self.assertEqual(True, bellman_ford(graph1, 'a'))
+    
+        graph2 = {
+            'a': {'d': 3, 'e': 4},
+            'b': {'a': 7, 'e':2},
+            'c': {'a': 12, 'd':9, 'e':11},
+            'd': {'c': 5, 'e': 11},
+            'e': {'a': 7, 'b': 5, 'd': 1}
+        } 
+    
+        self.assertEqual(True, bellman_ford(graph2, 'a'))

Original file line number	Diff line number	Diff line change
`@@ -1,2 +1,3 @@`
`1`	`1`	`from .tarjan import *`
`2`	`2`	`from .check_bipartite import *`
	`3`	`+from .bellman_ford import *`