[Algorithm] Dynamic Programming-2 (DAG shortest path)

1. Shortest paths in dags

Above graph is DAG(Directed Acyclic Graph).

We can linearization DAG 

Let dist(X) is the minmum distance from S to X.

To caclulate dist(D), comparing dist(C)+3 and dist(B)+1 is enough(because B and C are two predecessors to D).

Thus, dist(D)=min{dist(B)+1, dist(C)+3}

It means If we compute dist values in the left-to-right order, we can make sure that when we get to a node v, we already have all the information we need to compute dist(v).

 

Implement with python code:

from collections import defaultdict, deque

def shortest_path(graph, start):
    # Step 1: Compute the Topological Order of the Graph
    visited = defaultdict(bool)
    stack = deque()

    def topological_sort(node):
        visited[node] = True

        for neighbour in graph[node]:
            if not visited[neighbour]:
                topological_sort(neighbour)

        stack.appendleft(node)

    for node in graph:
        if not visited[node]:
            topological_sort(node)

    # Step 2: Compute shortest paths
    distances = defaultdict(lambda: float('inf'))
    distances[start] = 0

    while stack:
        node = stack.popleft()

        for neighbour in graph[node]:
            if distances[node] + graph[node][neighbour] < distances[neighbour]:
                distances[neighbour] = distances[node] + graph[node][neighbour]

    return distances

2. Longest increasing subsequences

Input : a sequence of numbers a1, …, an

A subsequence is any subset of these numbers taken in order, of the formai1, ai2,…, aikwhere1 ≤i1< i2<... < ik≤n

Goal : to find the increasing subsequence of greatest length.

E.g.) the longest increasing subsequence of 5, 2, 8, 6, 3, 6, 9, 7 : 2, 3, 6, 9