<jupyter_start><jupyter_text>Shortest Path Algorithms and Comparisons  IntroductionIn this tutorial, we will be covering the pros and cons of several shortest path algorithms that have been developed over the years. The shortest path problem can be defined as finding the minimum path between two points in a network, where the distance between two points is equal to the sum of all individual paths that connect these points together. To solve this problem, a common approach is to model the network in your problem with a graph data structure.  Tutorial ContentIn this tutorial, we will define a graph as a collection of ****nodes****, at which these nodes can be connected by ****edges****. Depending on what an edge means in the data model, an edge can either be ****unweighted**** or ****weighted****, from one node to another. Weighted edges simply means that there is a certain cost (that is **not** necessarily 1) to get from one vertex to another. For example, in a network of destination routes, an edge describing a route from Pittsburgh, PA to Philadelphia, PA, is obviously going to have considerably less weight than an edge describing a route from Pittsburgh, PA to Los Angeles, CA.Graphs can be represented in various ways: ****adjacency matrixes****, ****adjacency lists****, and ****nodes/pointers****. Depending on what problem you are trying to solve, some representations may be more fit than others. Graphs can also be ****directed**** or ****undirected****, where a directed graph is one in which an edge from node A to node B does not necessarily imply an edge from node 2 to node 1, whereas an undirected graph has those implications. Note that a directed graph can be an undirected graph, but not the other way around. For this tutorial, we will be using the default representation that NetworkX provides. Wait, I already know what graphs are, why did you have to explain so much above?There are quite a few shortest path algorithms out there, but why so many? Situational factors and optimization - or at least that's why I think so much effort has gone into the development of these algorithms. Depending on how you are presented with the data in the problem, sometimes it's better to model a graph with an adjacency matrix than other representations. And whether or not edges have weights turns out to have an affect on which shortest path algorithm will work. Likewise with a graph's directedness.Solving the shortest path problem will almost always be relevant in real world situations, so it helps to become familiar with these algorithms to focus your solutions at a higher level.In this tutorial, we will cover the following flavors of shortest path algorithms:  * Breadth-First Search  * Dijstrka's Algorithm  * Bellman-Ford Algorithm  * Floyd-Warshall Algorithm    For each of these algorithms, I will provide the sources that I used to help me write this tutorial.  What You'll NeedFor this tutorial, we will be using a Python package called NetworkX (https://github.com/networkx/networkx/). Although there are algorithms already provided in this library that let you do cool things with graphs (like the algorithms we're going to implement), we will primarily be using this package just to create our graphs.If your machine has Anaconda installed, you most likely already have this package. However, to ensure consistency with the upstream codebase, run the command:    $ pip install networkx --upgrade    Make sure the following import runs without any errors!<jupyter_code>import networkx as nx
import random
import matplotlib.pyplot as plt
import heapdict
from collections import deque
import sys<jupyter_output><empty_output><jupyter_text>Before we write code about algorithms that will help us solve the shortest path problem, we first need an actual graph to apply it on. Notice below that we will be creating two graphs: one that is undirected, and one that is directed. For simplicity, all the edges will have the same weight; this way, we'll be able to compare the outcomes of all the algorithms and see that they are the same. Also, we are creating our own Node class so that they can be marked if required by the algorithm.<jupyter_code>G = nx.Graph()
DG = nx.DiGraph()

class Node(object):
    def __init__(self,x):
        self.val = x
        self.visited = False

    def __repr__(self):
        return "<Node(%r)>" % self.val

# create some vertexes
for i in xrange(10):
    G.add_node(Node(i))
    DG.add_node(Node(i))
    
nodes = G.nodes()
dnodes = DG.nodes()

# Add edges both ways for the directed graph, so that it is similar to the 
# unweighted, undirected graph.
for i in xrange(1,9):
    G.add_edge(nodes[i-1],nodes[i])
    G.add_edge(nodes[i],nodes[i+1])
    G.add_edge(nodes[i],nodes[i/2])
    
    DG.add_edge(dnodes[i],dnodes[i/2],weight=1)
    DG.add_edge(dnodes[i/2],dnodes[i],weight=1)
    DG.add_edge(dnodes[i-1],dnodes[i], weight=1)
    DG.add_edge(dnodes[i],dnodes[i-1],weight=1)
    DG.add_edge(dnodes[i],dnodes[i+1], weight=1)
    DG.add_edge(dnodes[i+1],dnodes[i],weight=1)
    
# Uncomment the below lines if you want to see the graph
# nx.draw(DG)
# plt.show()<jupyter_output><empty_output><jupyter_text>**Utility functions**We'll be using the follow functions, as they will come in handy for re-use of code and displaying output.<jupyter_code>def trace_back(source,node,prevs):
    """
    Given a list of vertexes associated with their previous vertex, trace the node back to the
    source and print this path.
    Args:
        source : a node in the graph
        node : arbitrary node in the graph you want to have traced back to
        prevs : a key-val mapping of a node and it's previous path
    Output:
        path (list(Node)) : an in-order path from source to node
    """
    result = [node]
    while node in prevs and node != source:
        result.append(prevs[node])
        node = prevs[node]
    result.reverse()
    return result

def display_trace(source,dest,distance,path):
    print "Path from %r to %r with distance %d: %r" % (source,dest,distance,path)
    
def unmark(graph):
    """
    If using the same graph multiple times, and marking nodes, we want to ensure consistent
    output by unmarking the graph each time it is used.
    
    Args:
        graph : networkx.Graph that contains nodes of type(Node) that we defined above
    """
    for node in graph.nodes():
        node.visited = False

def weight(graph,from_node,to_node):
    """
    Return the weight of the edge (from_node,to_node). Defaults to +1 if no weight was specified
    during creation.
    Args:
        graph : networkx.Graph
        from_node : Node
        to_node : Node
    Output:
        int : cost of an edge
    """
    if 'weight' not in graph[from_node][to_node]:
        return 1
    return graph[from_node][to_node]['weight']<jupyter_output><empty_output><jupyter_text>Breadth-First Search Shortest PathA lot of search algorithms have some sort of origin from the Breadth-First Search algorithm. This is an algorithm that can get you started on a lot of graph problems. The gist of this algorithm is to keep track of neighbors of nodes with a queue, while traversing to unvisited nodes. Since the graph is unweighted, and we are traversing neighbors first, we are guaranteed to get the shortest path from any node to the source node.Restrictions:* **Unweighted graph*** No cycles in the graph<jupyter_code>def bfs_shortest_path(source,graph):
    """
    Input: source node in graph
    Output: list of distances, list of previous nodes
    """
    # Set all distances to a value recognized as infinity (in this case -1)
    distances = {node : -1 for node in graph.nodes()}
    previous = {node : None for node in graph.nodes()}
    
    # Set initial values for source distance and previous
    previous[source] = source
    distances[source] = 0
    
    # Mark the source as visited already
    source.visited = True
    
    # Initialize our queue with the source being the first node to examine
    q = deque()
    q.append(source)

    # Visit all nodes
    while len(q) > 0:
        
        # remove an unexamined node from the queue
        root = q.popleft()
        
        # search through all its neighbors
        for neighbor in graph.neighbors(root):
            if not neighbor.visited:
                # Unweighted graph, so we know the distance is just 1 away from where it came from
                distances[neighbor] = distances[root] + 1
                
                # Track the node where neighbor came from
                previous[neighbor] = root
                
                # Make sure we don't visit this node again
                neighbor.visited = True
                
                # Enqueue neighbor so that we can examine neighbor's neighbors
                q.append(neighbor)
    
    return distances,previous<jupyter_output><empty_output><jupyter_text>Here, we randomize a source node and a test (destination) node. Using the utility function `display_trace`, we can easily display our results that we get from these algorithms.<jupyter_code># Pick a random source node
sourcei = int(random.random()*(len(G.nodes())-1))

source_node,d_source_node = nodes[i],dnodes[i]

# Pick a random destination node
testi = int(random.random()*(len(G.nodes())-1))

test_node, d_test_node = nodes[testi],dnodes[testi]

# Since we are using the same graph throughout this tutorial, we must unmark vertices
# if we've marked them in one of these algorithms
unmark(G)

distances,previous = bfs_shortest_path(source_node,G)
path = trace_back(source_node,test_node,previous)
display_trace(source_node,test_node,distances[test_node],path)<jupyter_output>Path from <Node(5)> to <Node(2)> with distance 3: [<Node(5)>, <Node(1)>, <Node(8)>, <Node(2)>]<jupyter_text>Dijstrka's AlgorithmDijstrka's Algorithm is perhaps one of the most important graph search algorithms you can learn, simply because it is efficient, and relatively easy to implement (at least at a high level). The following algorithm will find the shortest path to a source node for *all* remaining nodes in directed and weighted graph, and in an efficient manner.The foundation of Dijstrka's Algorithm is Breadth-First search. We want to start from a source node, and then examine neighbors of unvisited nodes so that we can find the shortest possible path. However, in BFS, we simply used a queue: dequeuing off this data structure provides the program no implication of how "good" (read, "close") that node will be. Instead, in Dijstrka's Algorithm, we'll use a priority queue so that when we dequeue an unexamined node, we guarantee that we are looking at the closest possible node to the source at that moment. Using such a data structure drastically improves the efficiency as compared to plain BFS that was discussed above. In particular, we will be using the `heapdict` data structure, which internally decreases priorities when elements are removed. It is worth noting that if you are using the `heapq` package provided by Python, you'll have to implement a method that decreases priorities after an element gets taken out.Also take notice of the use of the weight() function: Dijstrka's Algorithm allows for weighted (although non-negative) edges.Restrictions:* Non-negative weights<jupyter_code>def dijstkras(source,graph):
    distances = {node : sys.maxsize for node in graph.nodes()}
    prevs = {node : None for node in graph.nodes()}
    pq = heapdict.heapdict()
    distances[source] = 0
    
    # put in all the nodes that aren't the source into the pq set
    for node in graph.nodes():
        pq[node] = distances[node]
    
    # Look through all nodes
    while len(pq) > 0:
        root_node, priority = pq.popitem()
        for neighbor in nx.all_neighbors(graph,root_node):
            if distances[root_node] == sys.maxsize:
                # If we haven't yet seen root_node, the difference is just the length from
                # the root to the neighbor
                diff = weight(root_node,neighbor,graph)
            else:
                # otherwise, we can add the distance to the root node
                diff = distances[root_node] + weight(graph,root_node,neighbor)
    
            if diff < distances[neighbor]:
                distances[neighbor] = diff
                prevs[neighbor] = root_node
                pq[neighbor] = diff # heapdict handles decreasing priority, so just set neighbor with new distance!
                
    return distances, prevs<jupyter_output><empty_output><jupyter_text>Our results are shown below.<jupyter_code>distances,previous = dijstkras(source_node,G)
path = trace_back(source_node,test_node,previous)
display_trace(source_node,test_node,distances[test_node],path)<jupyter_output>Path from <Node(5)> to <Node(2)> with distance 3: [<Node(5)>, <Node(9)>, <Node(3)>, <Node(2)>]<jupyter_text>Bellman-Ford AlgorithmThe Bellman-Ford Algorithm is an algorithm similar to Dijstrka's in the sense that it accomplishes the same job with a directed and weighted graph: getting the shortest distance between a source and all other nodes. Although this algorithm is slower than Dijstrka's, the Bellman-Ford Algorithm allows for negative weight edges, hence a reasonable trade-off in time complexity when used in the right situation. For example, you could be determining your net money spending when starting off with a certain amount, and see if you are capable of spending a certain amount of money (negative edge).The idea behind the Bellman-Ford Algorithm is to iterively improve the distances between nodes. Like Dijstrka's, we start off with destination and previous node initialization. From here, we must look at all edges, |V|-1 times, and see if each edge can be optimized. This works since you initialize each distance in the beginning to infinity, and then with each iteration in the outer loop, you continue to populate the distance array with better (if possible) and better distances between each edge.Pros:* **Allows negative weighted edges**Cons:* Slower than Dijstrka's Algorithm<jupyter_code>def bellman_ford_shortest_path(source,graph):
    # Initialize distances to the source node as infinity, or whatever you want to
    # have infinity be. Just be sure that you treat it as a "not yet visited" distance
    distances = {node: sys.maxsize for node in graph.nodes()}
    
    # Initialize the previous node that got to the current node. Used for path trace back
    prevs = {node: None for node in graph.nodes()}
    
    # Distance from source to the source is 0.
    distances[source] = 0

    num_vertexes = len(graph.nodes())
    
    # For |V|-1 nodes, see if the distances between the edges between the nodes
    # can decrease as you examine ALL the edges on each iteration. 
    for i in xrange(1,num_vertexes):
        for edge in graph.edges():
            from_node,to_node = edge
            w = weight(graph,from_node,to_node)
            if distances[from_node] != sys.maxsize and distances[from_node] + w < distances[to_node]:
                distances[to_node] = distances[from_node] + w
                prevs[to_node] = from_node

    for edge in graph.edges():
        from_node, to_node = edge
        if distances[from_node] + weight(graph,from_node,to_node) < distances[to_node]:
            raise Exception('Negative weight cycle detected!!')
    
    # What about negative weights?
    return distances,prevs
distances, previous = bellman_ford_shortest_path(d_source_node,DG)
path = trace_back(d_source_node,d_test_node,previous)
display_trace(d_source_node,d_test_node,distances[d_test_node],path)<jupyter_output>Path from <Node(0)> to <Node(9)> with distance 3: [<Node(0)>, <Node(8)>, <Node(7)>, <Node(9)>]<jupyter_text>Floyd-Warshall AlgorithmFor the purpose of exposure to more shortest path algorithms, I will show the Floyd-Warshall Algorithm that computes the shortest paths between *all* pairs of vertexes. This obviously requires a great deal of computation, so use it only when you need to.This algorithm takes advantage of dynamic programming, so that distances don't have to be recalculated over and over again. The algorithm lies on the idea that for every pair of node (i,j), there can be an intermediary node between them that reduces the distance between nodes i and k, and k and j, hence reducing the distance from i,j.This algorithm can be used for:* Weighted graphs (positive AND negative weights allowed)* No negative cyclesCons:* Computationally expensive (O( | of vertexes|^3 )<jupyter_code>def floyd_warshall_shortest_path(graph):
    num_vertexes = len(graph.nodes())
    distances = {node: {node : sys.maxsize for node in graph.nodes()} for node in graph.nodes()}
    
    # Distance from nodes to themselves should be 0. Treat this like the source distance
    # in the above algorithms.
    for node in graph.nodes():
        distances[node][node] = 0
    
    # Iniitilize the distances between edges with the weights for each edge
    for edge in graph.edges():
        distances[edge[0]][edge[1]] = weight(graph,edge[0],edge[1])
    
    nodes = graph.nodes()
    
    # For each intermediary node
    for node_k in nodes:
        
        # Get a source node
        for node_i in nodes:
            
            # Get a destination node
            for node_j in nodes:
                
                # Calculate the distance from i to k, and k to j
                intermediate_distance = distances[node_i][node_k] + distances[node_k][node_j]
                
                # decrease distance if we find an intermediary node that produces a smaller distance to i and j
                if distances[node_i][node_j] > intermediate_distance: 
                    distances[node_i][node_j] = intermediate_distance
                    
    return distances
pairs = floyd_warshall_shortest_path(DG)
print pairs[d_source_node][d_test_node]<jupyter_output>3
{'fraction_non_alphanumeric': 0.07139664804469274, 'fraction_numerical': 0.003798882681564246, 'mean_word_length': 3.5829493087557602, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 55, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '238067', 'license': 'MIT', 'n_tokens_mistral': 4891, 'n_tokens_neox': 4712, 'n_words': 2207, 'path': '2016/tutorial_final/147/tutorial.ipynb', 'repo_name': 'zeromtmu/practicaldatascience.github.io', 'size': '17900'}