Dijkstra's Algorithm

1. Introduction

Finds the shortest (lowest-cost) path through a graph from the start node to all other nodes.
This is the fastest, single-start, shortest path algorithm for directed and undirected networks with unbounded, non-negative edge weights.

2. Description of the algorithm

Set the current distance to 0 for your chosen beginning node and infinite for all other nodes.
Mark your beggining node
Set the current node C to the non-visited node with the shortest current distance.
For each neighbor N of your current node C, add the current distance of C to the weight of the edge connecting C-N. Set it as the new current distance of N if it is less than the current distance of N.
Mark the current node C as visited.
If there are non-visited nodes, go to step 2.

3. Dijkstra Pseudocode

This pseudocode is referred to the Florian's lecture.

term: V = vertex, pq = priority queue, St = staring node, Sp = predecessor, C = unvisited vertex, W = weight


    
        
            for each vertex V:
            initialize V's visited mark to false
        
        
            create minimum priority queue, pq, for vertices
        
        
            pq.insert( [St: Sp, 0 ])
    St = starting node, Sp = predeccessor node
    
    
        while ( !pq.isEmpty() ):
        [ C: Pred, Distance ] = pq.removeMinPathWeight()
        if C is unvisited:
        

            
                mark C as Visited, set predecessor to Previous Vertex, and cost to Distance in the graph
            
            
                for each edge with weight W to unvisited successor(US) of C:
                pq.insert( [ US: C, Distance + W ] )

4. The image that depicting the algorithm operates over

This image of a cute kitten is from a Medium post:An Introduction to Dijkstra’s Algorithm: Theory and Python Implementation