Dijkstra's

Dijkstra’s algorithm is a commonly used algorithm to determine the shortest path in a graph with non-negative weights. Its applications in logistics, communications and social networks include examples such as finding the cheapest path to send data packets between two machines on the internet or constructing an estimate of social distance for a simple recommender systems in a social network.

Graphs can be represented as adjacency matrices which requires a space complexity of $O(V^{2})$ assuming $V$ nodes. This format is suitable for dense graphs in which nodes are usually connected to a lot of other nodes in the graph. This is because while the space complexity is sizeable, looking up a value in the matrix is done in $O(1)$ time. Adjacency lists are another way to represent graphs. In this setting, each node is associated with a list containing the nodes that it is directly connected to resulting a space complexity of $O(V + E)$ where $V$ is the number of nodes and $E$ is the number of edges, however determining whether a node $v$ is connected to another node $u$ takes at most $O(V)$ time.

⊕Here I make use of an adjacency list to represent the graph. The elements of the list are tuples containing a neighbor and its distance from the key node. The specific values are taken from a test case of the ‘Bumped’ problem on Kattis.

G : dict = {
    0: [(1, 10), (2, 10)],
    1: [(2, 10), (3, 20), (4, 20)],
    2: [(6, 40)],
    3: [(4, 20), (5, 15), (6, 40)],
    4: [],
    5: [(6, 10)],
    6: [(7, 10)],
    7: []
    }

The algorithm starts by initializing the distance to the start node as $0$ as it ensure that it is the first node explored by Dijkstra’s. The example code below makes use of the heappop() method from the heapq which creates a sort of priority queue (i.e. a list which always pops out the element with the highest priority, in our case lowest distance as it is always the first element in the tuple). The algorithm explores the graph by visiting the node with the minimum (known) distance and updating the distance values of the unvisited nodes in the neighborhood of the current node.

import heapq

def dijkstra(G : dict, s):

    D = {v: float('inf') for v in G.keys()}; D[s] = 0
    P = {v: None for v in G.keys()}
    q = [(D[s], s)]

    while q:
        _, v = heapq.heappop(q)

        if _ > D[v]:
            continue

        for w, d in G[v]:
            if D[w] > D[v] + d:
                D[w] = D[v] + d
                P[w] = v
                heapq.heappush(q, (D[w], w))

    return D, P

The algorithm above returns the shortest distance to each node in the graph D and can be used to construct the shortest path to any node by recording the previous node that minimizes the distance P.

Recommendation System

One interesting application of Dijkstra’s algorithm is determing the social distance, or degree of separation, between two individuals in a social network (here I simply focus on social distance). The degree of separation is the metric used by LinkedIn to determine the first, second, or third degree of connection and to determine people that the social network could recommend to you.

⊕
Figure 1: Example of a social network.

The social network in Figure $1$ is a small network I created for a presentation. The edge weights are meant to represent some form of relationship strength in which lower edge weights values imply greater proximity. Here, Dijkstra’s algorithm can be used to determine the social distance between two nodes and classical graph traversal algorithms such as BFS can be used to compute the degree of connection. The table below provides an estimate of the proximity between all people in the network and Bob.

Frank and Carol are unreachable from Bob as they have no friends in common with Bob and thus their distance scores are set to infinity. These scores can be used to determine a list of potential friends to recommend to Bob. Individuals not yet connected to Bob but with low scores are natural candidates and examples include Laura and Xavier.