Dijkstra's Algorithm

1. Introduction

2. Description of the algorithm

  1. Set the current distance to 0 for your chosen beginning node and infinite for all other nodes.
  2. Mark your beggining node
  3. Set the current node C to the non-visited node with the shortest current distance.
  4. 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.
  5. Mark the current node C as visited.
  6. 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

  1. for each vertex V:

    initialize V's visited mark to false

  2. create minimum priority queue, pq, for vertices
  3. pq.insert( [St: Sp, 0 ])

    St = starting node, Sp = predeccessor node

  4. 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

Dijkstra's Algorithm