Friendpaste

--- Revision None
+++ Revision 376339343631
@@ -0,0 +1,77 @@
+def dijkstra(graph, start, end):
+    """
+    Dijkstra's algorithm Python implementation.
+    
+    Arguments:
+        graph: Dictionnary of dictionnary (keys are vertices).
+        start: Start vertex.
+        end: End vertex.
+    
+    Output:
+        List of vertices from the beggining to the end.
+        
+    Example:
+        
+    >>> graph = {
+    ...     'A': {'B': 10, 'D': 4, 'F': 10},
+    ...     'B': {'E': 5, 'J': 10, 'I': 17},
+    ...     'C': {'A': 4, 'D': 10, 'E': 16},
+    ...     'D': {'F': 12, 'G': 21},
+    ...     'E': {'G': 4},
+    ...     'F': {'H': 3},
+    ...     'G': {'J': 3},
+    ...     'H': {'G': 3, 'J': 5},
+    ...     'I': {},
+    ...     'J': {'I': 8},
+    ... }    
+    >>> dijkstra(graph, 'C', 'I')
+    ['C', 'A', 'B', 'I']
+    
+    """
+    
+    D = {} # Final distances dict
+    P = {} # Predecessor dict
+    
+    # Fill the dicts with default values
+    for node in graph.keys():
+        D[node] = -1 # Vertices are unreachable
+        P[node] = "" # Vertices have no predecessors
+        
+    D[start] = 0 # The start vertex needs no move
+    
+    unseen_nodes = graph.keys() # All nodes are unseen
+    
+    while len(unseen_nodes) > 0:
+        # Select the node with the lowest value in D (final distance)
+        shortest = None
+        node = ''
+        for temp_node in unseen_nodes:
+            if shortest == None:
+                shortest = D[temp_node]
+                node = temp_node
+            elif D[temp_node] < shortest:
+                shortest = D[temp_node]
+                node = temp_node
+                
+        # Remove the selected node from unseen_nodes
+        unseen_nodes.remove(node)
+        
+        # For each child (ie: connected vertex) of the current node
+        for child_node, child_value in graph[node].items():
+            if D[child_node] < D[node] + child_value:
+                D[child_node] = D[node] + child_value
+                # To go to child_node, you have to go through node
+                P[child_node] = node
+                
+    # Set a clean path
+    path = []
+    
+    # We begin from the end
+    node = end
+    # While we are not arrived at the beggining
+    while not (node == start):
+        path.insert(0, node) # Insert the predecessor of the current node
+        node = P[node] # The current node becomes its predecessor
+    
+    path.insert(0, start) # Finally, insert the start vertex
+    return path
a	b
	0	+	def dijkstra(graph, start, end):
	0	+	"""
	0	+	Dijkstra's algorithm Python implementation.
	0	+
	0	+	Arguments:
	0	+	graph: Dictionnary of dictionnary (keys are vertices).
	0	+	start: Start vertex.
	0	+	end: End vertex.
	0	+
	0	+	Output:
	0	+	List of vertices from the beggining to the end.
	0	+
	0	+	Example:
	0	+
	0	+	>>> graph = {
	0	+	... 'A': {'B': 10, 'D': 4, 'F': 10},
	0	+	... 'B': {'E': 5, 'J': 10, 'I': 17},
	0	+	... 'C': {'A': 4, 'D': 10, 'E': 16},
	0	+	... 'D': {'F': 12, 'G': 21},
	0	+	... 'E': {'G': 4},
	0	+	... 'F': {'H': 3},
	0	+	... 'G': {'J': 3},
	0	+	... 'H': {'G': 3, 'J': 5},
	0	+	... 'I': {},
	0	+	... 'J': {'I': 8},
	0	+	... }
	0	+	>>> dijkstra(graph, 'C', 'I')
	0	+	['C', 'A', 'B', 'I']
	0	+
	0	+	"""
	0	+
	0	+	D = {} # Final distances dict
	0	+	P = {} # Predecessor dict
	0	+
	0	+	# Fill the dicts with default values
	0	+	for node in graph.keys():
	0	+	D[node] = -1 # Vertices are unreachable
	0	+	P[node] = "" # Vertices have no predecessors
	0	+
	0	+	D[start] = 0 # The start vertex needs no move
	0	+
	0	+	unseen_nodes = graph.keys() # All nodes are unseen
	0	+
	0	+	while len(unseen_nodes) > 0:
	0	+	# Select the node with the lowest value in D (final distance)
	0	+	shortest = None
	0	+	node = ''
	0	+	for temp_node in unseen_nodes:
	0	+	if shortest == None:
	0	+	shortest = D[temp_node]
	0	+	node = temp_node
	0	+	elif D[temp_node] < shortest:
	0	+	shortest = D[temp_node]
	0	+	node = temp_node
	0	+
	0	+	# Remove the selected node from unseen_nodes
	0	+	unseen_nodes.remove(node)
	0	+
	0	+	# For each child (ie: connected vertex) of the current node
	0	+	for child_node, child_value in graph[node].items():
	0	+	if D[child_node] < D[node] + child_value:
	0	+	D[child_node] = D[node] + child_value
	0	+	# To go to child_node, you have to go through node
	0	+	P[child_node] = node
	0	+
	0	+	# Set a clean path
	0	+	path = []
	0	+
	0	+	# We begin from the end
	0	+	node = end
	0	+	# While we are not arrived at the beggining
	0	+	while not (node == start):
	0	+	path.insert(0, node) # Insert the predecessor of the current node
	0	+	node = P[node] # The current node becomes its predecessor
	0	+
	0	+	path.insert(0, start) # Finally, insert the start vertex
	0	+	return path
...