Paris on the chair

• Topological sort (acyclic graph, adjacency list) - O(V+E)

Topological Sort (위상정렬)

그래프는 정점들을 간선을 통해 모든 관계를 표현한다.

 위상 정렬은 그래프에서 정점을 정렬함을 의미한다.

위상정렬이 Optimal 을 만족하기 위해서는 

아래 제약조건을 만족해야한다.

1. 방향성이 존재 (Directed)

2. Cycle이 존재하지 않아야 한다. (Asyclic)

How to solve ?

핵심은 'In degree'가 0인 정점을 출력하는 것.

구현은 아래  1 -> 2 패턴을 반복한다.

1. In degree가 0인 정점들을 우선 정렬한다.

(In degree  == 0 : 다른 정점의 Dependency가 없기 때문에 출력해도 괜찮은 상태를 의미.)

2. In degree를 갱신한다.

(이미 정렬한 정점 관련 Dependency 갱신)

Data Structure는 Stack이든 Queue든 차이가 없다.

In degree 가 0인 정점을 우선적으로 채택한다는 단순성에서

Greedy Algorithm으로 분류하고 싶다.

##########################
###### pseudo code. ######
##########################

def TopologicalSort(graph, V: int) -> List:
""" @param
    graph: adjacency-list. or 2d mat. assumed adjacency-list in this pseudo.
    
           i.e. 
              if you construct graph as adjacency-list -> O(E+V)
              if you construct graph as 2D-Mat -> O(V^2)	

           e.g. graph[0] = [1,2,3] :    3
                                        ^
                                        |
                                        0 -> 1
                                        ↓
                                        2
            

    V: the number of vertexes

"""
    res = [] # sort된 list를 반환한다.
    
    # Edge로부터 Direction을 받는 노드들의 개수를 초기화
    in_degree = [0] * V
    for from, edge in enumerate(graph):
        for to in edge:
            in_degree[to] += 1
    
    visit = [False] * V
    q = Queue() # this can be replaced with 'list', 'stack' ..
    for n in Range(V):
        if in_degree[n] == 0:
            visited[n] = True
            q.push(n)
    
    while !q.empty():
    	cur_node = q.get()
        res.append(cur_node)
        
        for adj_node in graph[cur_node]:
            in_degree[adj_node] -= 1
            if in_degree[adj_node] == 0:
            	q.push(adj_node)
               
    return res

• Bellman-Ford (adjacency list, negative cycles) - O(VE)
• Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)

Bellman Ford Algorithm Key Features

1. Start 노드를 규정하고 다른 모든 노드들의 최단 거리를 계산하는 알고리즘이다.

( SSSP Algorithm; Single Source Shortest Path)

2. 음의 간선이 존재해도 동작한다.

Brief Steps for finding shortest Path 

1. src (start) 이외의 모든 노드의 비용을 양의 무한대로 초기화 한다.

2. v-1 회만큼 모든 Edge를 순회하며 아래 조건을 반복한다. (이 단계를 'relaxation' 이라 함)

- if dist[edge.from] + edge.cost <  dist[edge.cost]

             dist[edge.to] = dist[edge.from] + edge.cost

3. (2) 조건을 한번 더 반복하여 relaxation이 가능한 노드를 확인한다.

* relaxation 과정의 outer-loop는 왜 v-1 번 수행하는가 ? 

->  모든 Edge에 대해 한번의 순회의 계산은, Path에서 최소 1번의 Edge를 거치는 Shortest Path의 안정화를 보장한다. 

즉, i번의 순회는 최소 i개의 edge를 거치는 Shorterst Path를 안정화 보장시킨다는 의미이고,

Path는 최대 V-1개의 Edge를 갖을 수 있으므로 outer loop는 v-1 회 반복해야한다.

• Bellman-Ford (adjacency list, negative cycles) - O(VE)

# pseudo code 

def bellmanFord(src: int, edges: List[Edge]) -> list:
    distances = [POSITIVE_INF] * n
    distances[src] = 0
    
    # relaxation
    for _ in range(v-1): # v is the number of vertexies
        for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = distances[edge.from] + edge.cost
     
    # detect negative-cycle.
    for _ in range(v-1): # v is the number of vertexies
        for edge in edges:
            # The node is in negative-cycle if it is possible to relaxation
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = NEGATIVE_INF

    return distances

Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)

최적화 아이디어는 굉장히 간단하다. 

앞서 설명했듯, 순회문이 V-1인 이유는 Worst Case를 염두에 두기 때문이다.

이를 감지하는 Boolean을 두면 최적화 여지가 있다.

# pseudo code 

def bellmanFord(src: int, edges: List[Edge]) -> list:
    distances = [POSITIVE_INF] * n
    distances[src] = 0
    bool relaxed # here !
    
    # relaxation
    for _ in range(v-1):
    	relaxed = False # here !
    	for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = distances[edge.from] + edge.cost
                relaxed = True # here ! 
     	
        if relaxed == False: # relaxation 이 없었으면, 순회문을 반복할 이유가 없다.
            break

    # detect negative-cycle.
    for _ in range(v-1):
    	relaxed = False
        for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = NEGATIVE_INF
                relaxed = True # here !
                
        if relaxed == False: # here !
            break

    return distances

• Dijkstra Shortest Path (Just use priority queue + 2d Matrix) - O(V^2 * log(V)) => stay here !
• Dijkstra Shortest Path (Just use priority queue + adjancylist) - O(Elog(V)) - - - -  basic way => stay here !
• Dijkstra shortest Path (Indexed Priority Queue + adjancylist + D-arr heap) - O(ElogE/V(V))
• Dijkstra shortest Path (fibonacci heap) - O(E+Vlog(V))

Dijkstra Key Features

1. Start 노드 규정하고 다른 모든 노드들의 최단 거리를 계산하는 알고리즘이다.

2. 다익스트라는 Greedy에 기반한 알고리즘으로 모든 그래프 Edge는 음수가 되어서는 안된다. 

Dijkstra Shortest Path (priority queue + 2D Matrix)

# pseudo code

# graph[A][B] means the distance from A to B.
def dijkstra(start, graph: List[List[]]) -> Float:
    distance = [INF] * n # n is the size of node [INF,INF,INF ...]
    distance[start] = 0
    
    # you should implement pq with key-value pair
    # key is the node index (unique)
    # value is the given distance 
    # pq should build min-heap based on value.
    # then, the pq tell you which node to visit next (greedy!)
    pq = priority_queue()
    pq.insert((start,0)) 
    
    while !pq.empty():
    	cur_node, dist = pq.get()
        pq.pop() # the get() of python implicitly runs pop(), but most aren't.
        
        if distance[cur_node] < dist: # the better path is already calculated
            continue
            
        for (int adj_node_idx=0; adj_node_idx < n; adj_node_idx++):
            if graph[cur_node][adj_node_idx] == INF:
                continue
    
            new_cost = dist + graph[cur_node][adj_node_idx]
            if new_cost < distance[adj_node_idx]:# unnecessary if not in this caluse, the better path already is in the pq.
                distance[adj_node_idx] = new_cost
                pq.push(adj_node_idx, new_cost)
                
     return distance

만약 반환 값으로 최단 경로[List]가 필요한 경우 아래와 같다.

# pseudo code

# graph[A][B] means the distance from A to B.
def dijkstra(start, graph: List[List[]]) -> list:
    distance = [INF] * n 
    distance[start] = 0
    get_parent = {start: NONE} # here !

    pq = priority_queue()
    pq.insert((start,0)) 
    
    while !pq.empty():
    	cur_node, dist = pq.get()
        pq.pop()
        
        if distance[cur_node] < dist: 
            continue
            
        for (int adj_node_idx=0; adj_node_idx < n; adj_node_idx++):
            if graph[cur_node][adj_node_idx] == INF:
                continue
    
            new_cost = dist + graph[cur_node][adj_node_idx]
            if new_cost < distance[adj_node_idx]:
                distance[adj_node_idx] = new_cost
                get_parent[adj_node_idx] = cur_node # here !
                pq.push(adj_node_idx, new_cost)
                
     return get_parent

# usage example
def main():
    get_parent = dijkstra(start,Graph)
    path = []
    node = target # the target node_index that you want to get path from start
    while node is not NONE:
    	path.append(node)
        node = get_parent[node]
    path = path[:-1]

Dijkstra Shortest Path (priority queue + Adjacency List)

# pseudo code 

def dijkstra(start: int, adjacency_node: List[List[]], adjacency_dist: List[List[]]):
    """
    e.g.
        adjacency_node[0] = [1,5]
        adjacency_cost[0] = [12,23]

        node idx 0 -> 1 , 0 -> 5 로 갈 수 있으며 각각의 distance는 12,23
    """
    distance = [INF] * n # n is the size of the node
    distance[start] = 0
    
    # key (node idx) - value (distance) 
    # min_heap adhered to value
    pq = priority_queue() 
    pq.insert((start,0))
    
    while !pq.empty():
    	cur_node, cur_dist = pq.get()
        pq.pop()
        
        # neat optimization 
        if distance[cur_node] < cur_dist:
            continue
 
        for idx, adj_node in enumerate(adjacency_list[cur_node]):
            adj_cost = adjacency_dist[cur_node][idx]
            new_cost = cur_dist + adj_cost
            if distance[adj_node] > new_cost: 
                distance[adj_node] = new_cost
                pq.insert((adj_node,new_cost))
                
     return distance