Dijkstra's Shortest Path Algorithm

• 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