Module 10
Heaps and Priority Queues
Dijkstra's Algorithm

CC315 Fall 2020

Dijkstra's Algorithm

Goal: given an input node, find the shortest path to all other nodes.

Dijkstra's Algorithm

DIJKSTRAS(GRAPH, SRC)
    SIZE = size of GRAPH
    DISTS = array with length equal to SIZE
    PREVIOUS = array with length equal to SIZE
    set all of the entries in PREVIOUS to none
    set all of the entries in DISTS to infinity 
    DISTS[SRC] = 0 
    PQ = min-priority queue
    loop IDX starting at 0 up to SIZE
        insert (DISTS[IDX],IDX) into PQ
    while PQ is not empty
        MIN = REMOVE-MIN from PQ
        for NODE in neighbors of MIN
            WEIGHT = graph weight between MIN and NODE
            CALC = DISTS[MIN] + WEIGHT
            if CALC < DISTS[NODE]
                DISTS[NODE] = CALC
                PREVIOUS[NODE] = MIN
                PQ decrease-key (CALC, NODE)
    return DISTS and PREVIOUS

Dijkstra's Algorithm

DIJKSTRAS(GRAPH, SRC)
    SIZE = size of GRAPH
    DISTS = array with length equal to SIZE
    PREVIOUS = array with length equal to SIZE
    set all of the entries in PREVIOUS to none
    set all of the entries in DISTS to infinity 
    DISTS[SRC] = 0 
    PQ = min-priority queue
    loop IDX starting at 0 up to SIZE
        insert (DISTS[IDX],IDX) into PQ
    while PQ is not empty
        MIN = REMOVE-MIN from PQ
        for NODE in neighbors of MIN
            WEIGHT = graph weight between MIN and NODE
            CALC = DISTS[MIN] + WEIGHT
            if CALC < DISTS[NODE]
                DISTS[NODE] = CALC
                PREVIOUS[NODE] = MIN
                PQ decrease-key (CALC, NODE)
    return DISTS and PREVIOUS

Dijkstra's Algorithm

DIJKSTRAS(GRAPH, SRC)
    SIZE = size of GRAPH
    DISTS = array with length equal to SIZE
    PREVIOUS = array with length equal to SIZE
    set all of the entries in PREVIOUS to none
    set all of the entries in DISTS to infinity 
    DISTS[SRC] = 0 
    PQ = min-priority queue
    loop IDX starting at 0 up to SIZE
        insert (DISTS[IDX],IDX) into PQ
    while PQ is not empty
        MIN = REMOVE-MIN from PQ
        for NODE in neighbors of MIN
            WEIGHT = graph weight between MIN and NODE
            CALC = DISTS[MIN] + WEIGHT
            if CALC < DISTS[NODE]
                DISTS[NODE] = CALC
                PREVIOUS[NODE] = MIN
                PQ decrease-key (CALC, NODE)
    return DISTS and PREVIOUS

Dijkstra's Algorithm

DIJKSTRAS(GRAPH, SRC)
    SIZE = size of GRAPH
    DISTS = array with length equal to SIZE
    PREVIOUS = array with length equal to SIZE
    set all of the entries in PREVIOUS to none
    set all of the entries in DISTS to infinity 
    DISTS[SRC] = 0 
    PQ = min-priority queue
    loop IDX starting at 0 up to SIZE
        insert (DISTS[IDX],IDX) into PQ
    while PQ is not empty
        MIN = REMOVE-MIN from PQ
        for NODE in neighbors of MIN
            WEIGHT = graph weight between MIN and NODE
            CALC = DISTS[MIN] + WEIGHT
            if CALC < DISTS[NODE]
                DISTS[NODE] = CALC
                PREVIOUS[NODE] = MIN
                PQ decrease-key (CALC, NODE)
    return DISTS and PREVIOUS

Dijkstra's Algorithm

DIJKSTRAS(GRAPH, SRC)
    SIZE = size of GRAPH
    DISTS = array with length equal to SIZE
    PREVIOUS = array with length equal to SIZE
    set all of the entries in PREVIOUS to none
    set all of the entries in DISTS to infinity 
    DISTS[SRC] = 0 
    PQ = min-priority queue
    loop IDX starting at 0 up to SIZE
        insert (DISTS[IDX],IDX) into PQ
    while PQ is not empty
        MIN = REMOVE-MIN from PQ
        for NODE in neighbors of MIN
            WEIGHT = graph weight between MIN and NODE
            CALC = DISTS[MIN] + WEIGHT
            if CALC < DISTS[NODE]
                DISTS[NODE] = CALC
                PREVIOUS[NODE] = MIN
                PQ decrease-key (CALC, NODE)
    return DISTS and PREVIOUS

Dijkstra's Algorithm

DIJKSTRAS(GRAPH, SRC)
    SIZE = size of GRAPH
    DISTS = array with length equal to SIZE
    PREVIOUS = array with length equal to SIZE
    set all of the entries in PREVIOUS to none
    set all of the entries in DISTS to infinity 
    DISTS[SRC] = 0 
    PQ = min-priority queue
    loop IDX starting at 0 up to SIZE
        insert (DISTS[IDX],IDX) into PQ
    while PQ is not empty
        MIN = REMOVE-MIN from PQ
        for NODE in neighbors of MIN
            WEIGHT = graph weight between MIN and NODE
            CALC = DISTS[MIN] + WEIGHT
            if CALC < DISTS[NODE]
                DISTS[NODE] = CALC
                PREVIOUS[NODE] = MIN
                PQ decrease-key (CALC, NODE)
    return DISTS and PREVIOUS

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example

Dijkstra's Example