Repository: keon/algorithms
Pull request #270 (2018-05-01 18:59:00)

Dijkstra's single source shortest path algorithm
A popular algorithm that returns shortest path to all vertices from the source vertex.

coveralls: ## Pull Request Test Coverage Report for [Build 215](https://coveralls.io/builds/16782604)

* **0** of **0**  **(NaN%)** changed or added relevant lines in **0** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage remained the same at **91.076%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/16782604/badge)](https://coveralls.io/builds/16782604) |
| :-- | --: |
| Change from base [Build 214](https://coveralls.io/builds/16766416): |  0.0% |
| Covered Lines: | 2674 |
| Relevant Lines: | 2936 |

---
##### 💛  - [Coveralls](https://coveralls.io)

danghai: Good! Could you provide the `unittest` for this algorithm? 
agranya99: Sure, will do it.

On Wed, May 2, 2018, 3:58 AM Hai Hoang Dang <notifications@github.com>
wrote:

> Good! Could you provide the unittest for this algorithm?
>
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/keon/algorithms/pull/270#issuecomment-385809581>, or mute
> the thread
> <https://github.com/notifications/unsubscribe-auth/AhtBSpK9CJiXu32pEu5hmyLgI3y0o22uks5tuOGqgaJpZM4TuWHE>
> .
>

danghai: @goswami-rahul shoud we add the reference about the source? 
agranya99: @goswami-rahul Thanks for the suggestions. Have made the suggested changes.
danghai: Nice addition of Stack! . But some changes are required. Thanks
danghai: @agranya99 I update something in your `order_stack`. 
goswami-rahul: @agranya99 The tests are failed because of some indentation error. Please use 4 spaces everywhere, and don't mix them with tabs (see your IDE settings for this).

Patch:
diff --git a/README.md b/README.md
index 8d3332e..660369f 100644
--- a/README.md
+++ b/README.md
@@ -32,7 +32,7 @@ For running all tests write down:
 ## Install
 If you want to use the API algorithms in your code, it is as simple as:
 
-    $ pip3 install .
+    $ pip3 install git+https://github.com/keon/algorithms
 
 You can test by creating a python file: (Ex: use `merge_sort` in `sort`)
 
diff --git a/graph/dijkstra.py b/graph/dijkstra.py
new file mode 100644
index 0000000..fe5772e
--- /dev/null
+++ b/graph/dijkstra.py
@@ -0,0 +1,36 @@
+#Dijkstra's single source shortest path algorithm
+
+class Graph():
+
+    def __init__(self, vertices):
+        self.vertices = vertices
+        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]
+
+    def min_distance(self, dist, min_dist_set):
+        min_dist = float("inf")
+        for v in range(self.vertices):
+            if dist[v] < min_dist and min_dist_set[v] == False:
+                min_dist = dist[v]
+                min_index = v
+        return min_index
+
+    def dijkstra(self, src):
+
+        dist = [float("inf")] * self.vertices
+        dist[src] = 0
+        min_dist_set = [False] * self.vertices
+
+        for count in range(self.vertices):
+
+            #minimum distance vertex that is not processed
+            u = self.min_distance(dist, min_dist_set)
+
+            #put minimum distance vertex in shortest tree
+            min_dist_set[u] = True
+
+            #Update dist value of the adjacent vertices
+            for v in range(self.vertices):
+                if self.graph[u][v] > 0 and min_dist_set[v] == False and dist[v] > dist[u] + self.graph[u][v]:
+                    dist[v] = dist[u] + self.graph[u][v]
+
+        return dist
diff --git a/queues/priority_queue.py b/queues/priority_queue.py
new file mode 100644
index 0000000..92d8c4a
--- /dev/null
+++ b/queues/priority_queue.py
@@ -0,0 +1,41 @@
+"""
+Implementation of priority queue
+"""
+
+class PriorityQueueNode:	
+	def __init__(self, data, priority):
+		self.data = data
+		self.priority = priority
+
+	def __repr__(self):
+		return str(self.data) + ": " + str(self.priority)
+
+class PriorityQueue:
+	def __init__(self):
+		self.priority_queue_list = []
+
+	def size(self):
+		return len(self.priority_queue_list)
+
+	def insert(self, node):
+		# if queue is empty
+		if self.size() == 0:
+			self.priority_queue_list.append(node)
+		else:
+			 # traverse the queue to find the right place for new node
+			 for index, current in enumerate(self.priority_queue_list):
+			 	if current.priority < node.priority:
+			 		# if we have traversed the complete queue
+			 		if index == self.size() - 1:
+			 			# add new node at the end
+			 			self.priority_queue_list.insert(index + 1, node)
+			 		else:
+			 			continue
+			 	else:
+			 		self.priority_queue_list.insert(index, node)
+			 		return True
+
+	def delete(self):
+		# remove the first node from the queue
+		return self.priority_queue_list.pop(0)
+										
\ No newline at end of file
diff --git a/stack/ordered_stack.py b/stack/ordered_stack.py
new file mode 100644
index 0000000..7a30d14
--- /dev/null
+++ b/stack/ordered_stack.py
@@ -0,0 +1,33 @@
+#The stack remains always ordered such that the highest value is at the top and the lowest at the bottom
+
+class OrderedStack:
+     def __init__(self):
+         self.items = []
+
+     def is_empty(self):
+         return self.items == []
+
+     def push_t(self, item):
+         self.items.append(item)
+
+     def push(self, item): #push method to maintain order when pushing new elements
+         temp_stack = OrderedStack()
+         if self.is_empty() or item > self.peek():
+             self.push_t(item)
+         else:
+             while item < self.peek() and not self.is_empty():
+                 temp_stack.push_t(self.pop())
+             self.push_t(item)
+             while not temp_stack.is_empty():
+                 self.push_t(temp_stack.pop())
+
+     def pop(self):
+         if self.is_empty():
+             raise IndexError("Stack is empty")
+         return self.items.pop()
+
+     def peek(self):
+         return self.items[len(self.items) - 1]
+
+     def size(self):
+         return len(self.items)


Test patch:
diff --git a/tests/test_stack.py b/tests/test_stack.py
index 3b55ac9..e3b85d4 100644
--- a/tests/test_stack.py
+++ b/tests/test_stack.py
@@ -6,6 +6,7 @@ from stack.switch_pairs import first_switch_pairs, second_switch_pairs
 from stack.valid_parenthesis import is_valid
 from stack.simplify_path import simplify_path
 from stack.stack import ArrayStack, LinkedListStack
+from stack.ordered_stack import OrderedStack
 
 import unittest
 class TestSuite(unittest.TestCase):
@@ -129,5 +130,19 @@ class TestStack(unittest.TestCase):
 
         self.assertTrue(stack.is_empty())
 
+class TestOrderedStack(unittest.TestCase):
+    def test_OrderedStack(self):
+        stack = OrderedStack()
+        self.assertTrue(stack.is_empty())
+        stack.push(1)
+        stack.push(4)
+        stack.push(3)
+        stack.push(6)
+        "bottom - > 1 3 4 6 "
+        self.assertEqual(6, stack.pop())
+        self.assertEqual(4, stack.peek())
+        self.assertEqual(3, stack.size())
+
+
 if __name__ == "__main__":
     unittest.main()