Introduction to Dijkstra's Algorithm

Estimated Time

1 hour

Motivation

Everyone wants to reach the destination as fast as possible – Anonymous

Introduction

Introduction video for Dijkstra’s Algorithm

Prerequisites of the Experiment

This experiment requires you to have basic knowledge about :

  • Basic knowledge of graphs (data structure)
  • Familiarity with data structures such as queues and priority queues.
  • Calculation of basic time and space complexity.
  • Intuition about the Greedy Choice Algorithms
  • Knowledge about Graph Traversal Algorithms
  • And above all, a curiosity to learn and explore..!
Click on the above links for a short video elaborating each of the concepts.

Overview of the Experiment

  • The aim of this experiment is to understand the Dijkstra’s Shortest Path algorithm, its time and space complexity, and how it compares against other shortest path algorithms.
  • The experiment features a series of modules with video lectures,interactive demonstrations, simulations, hands-on practice exercises and quizzes to self analyze.

Learning Objectives of the Experiment

In this experiment on Dijkstra's Shortest Path algorithm, you will learn following:

  • (Understanding) Student is able to describe 2 real-world scenarios where shortest path algorithms are required.
  • (Remembering) Can recall the time complexity of graph traversal.
  • (Applying) Can analyze the problem and choose suitable shortest path algorithm.
  • (understanding) Understands the intuition of the algorithm and hence can implement the underlying data structures required.
  • (understanding) Can visually demonstrate the steps followed by Dijkstra’s Shortest Path Algorithm.
  • (understanding) Can recall and derive the space and time complexity of the Dijkstra’s Algorithm.
  • (applying) Can apply Dijkstra’s Algorithm in real world problems.

Experiment Modules and their Weightage

Module Weightage Expectation
Pre-test 5% Solve All Questions
Shortest Path Algorithms 15% Answer the Conceptual questions
The Dijkstra Algorithm 30% Try all operations with atleast two examples
Applications 25% Applying the concept to solve a problem
Post-assessment 25% Solve All Questions

Pre-test of the Experiment

Estimated Time

20 minutes

Instructions for Pre-Test

  • Pretest includes questions on graphs, queues, priority queues and time and space complexity.
  • If you want to revise these topics before taking the quiz, go through the recap module first.
  • Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Quick look at Graphs, Queues, Greedy choice algorithms

Graphs

Graphs are mathematical structures that represent pairwise relationships between objects. A graph is a flow structure that represents the relationship between various objects. It can be visualized by using the following two basic components:

  1. Nodes: These are the most important components in any graph. Nodes are entities whose relationships are expressed using edges. If a graph comprises 2 nodes and an undirected edge between them, then it expresses a bi-directional relationship between the nodes and edge.
  2. Edges: Edges are the components that are used to represent the relationships between various nodes in a graph. An edge between two nodes expresses a one-way or two-way relationship between the nodes.

Undirected graph

Picture shows undirected graphs.

Directed graph

Picture shows directed graphs.

Queues

Queues are data structures that follow the First In First Out (FIFO) i.e. the first element that is added to the queue is the first one to be removed. Elements are always added to the back and removed from the front. Think of it as a line of people waiting for a bus. The person who is at the beginning of the line is the first one to enter the bus.
Queues support the following fundamental functions:

  1. Enqueue: If the queue is not full, this function adds an element to the back of the queue, else it prints “OverFlow”.
  2. Dequeue: If the queue is not empty, this function removes the element from the front of the queue, else it prints “UnderFlow”.
  3. Front: This function returns the front element of the queue.

Functions related to queues

Picture demonstrates functions related to queues.

Time and Space Complexity

Time complexity of an algorithm gives the measure of time taken by it to run as a function of the length of the input. Similarly, Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.

A Quiz with Multiple Choice Questions

Q1. Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even?

(A) P Only

(B) Q Only

(C) Both P and Q

(D) Neither P nor Q

P is true for undirected graph as adding an edge always increases degree of two vertices by 1.
Q is true: If we consider sum of degrees and subtract all even degrees, we get an even number because every edge increases the sum of degrees by 2. So total number of odd degree vertices must be even.

Q2. Which of the following data structure is useful in traversing a given graph by breadth first search?

(A) Stack

(B) List

(C) Queue

(D) None of these

BFS performs level-order traversal which can be fairly done using a queue. A queue uses FIFO ordering and the nodes that we enqueue first are explored first maintaining the order of traversal.

Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

(A) X will always be a better choice for small inputs

(B) X will always be a better choice for large inputs

(C) Y will always be a better choice for small inputs

(D) X will always be a better choice for all inputs

Performance could be similar for small inputs, but definitely better for larger inputs

Q4. What is the time and space complexity for the given code?


int a = 0, b = 0; 
for (i = 0; i< N; i++) {
  a = a + rand(); 
}
for (j = 0; j< M; j++) {
  b = b + rand(); 
}
												
											

(A) O(N * M) time, O(1) space

(B) O(N + M) time, O(N + M) space

(C) O(N + M) time, O(1) space

(D) O(N * M) time, O(N + M) space

The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.

Q5. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?

(A) v=e

(B) v = e+1

(C) v + 1 = e

(D) v = e-1

For any connected graph with no cycles the equation holds true.

Dijkstra’s Algorithm

Estimated Time

30 minutes

Dijkstra’s Algorithm overview

Video giving a brief overview of Dijkstra’s Algorithm

Learning Objectives of this Module:

In this module, we will learn about:

  1. Need for Single Source Shortest Path algorithms
  2. Intuition for Dijkstra’s algorithm
  3. How to apply Dijkstra’s algorithm
  4. Practice the Algorithm
  5. Conceptual understanding with a short quiz

Understanding the Dijkstra's Algorithm

The Problem

  • In many applications one wants to obtain the shortest path from a to b.
  • Depending on the context, the length of the path does not necessarily have to be the length in meter:
  • One can as well look at the cost of a path – both if we have to pay for using it – or if we receive some. In general we speak of cost.Therefore one assigns cost to each part of the path – also called "edge".
  • Dijkstra's Algorithm computes shortest – or cheapest paths, if all cost are positive numbers.
  • However, if one allows negative numbers, the algorithm will fail.
  • Other single source shortest path algorithms

    Let's take note of other single source shortest path algorithms and their Applications:

    • Bellman–Ford algorithm: The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.
      Like Dijkstra's algorithm, Bellman–Ford proceeds by relaxation, in which approximations to the correct distance are replaced by better ones until they eventually reach the solution.
    • BFS algorithm:If the graph is unweighted, we can solve this problem in O(V + E) time. The idea is to use a modified version of Breadth-first search in which we keep storing the predecessor of a given vertex while doing the breadth first search. This algorithm will work even when negative weight cycles are present in the graph.

    Why and where Dijkstra’s Algorithm is used?

    Dijkstra’s algorithm is used when the graph has positive weights only. It is faster than the above other single source shortest path algorithms.

    Demonstration for Dijkstra's Algorithm

    Dijkstra's Algorithm

    Video for Dijkstra's Algorithm

    Dijkstra's Algorithm

    1. Set the distance to the source to 0 and the distance to the remaining vertices to infinity.
    2. Set the current vertex to the source.
    3. Flag the current vertex as visited.
    4. For all vertices adjacent to the current vertex, set the distance from the source to the adjacent vertex equal to the minimum of its present distance and the sum of the weight of the edge from the current vertex to the adjacent vertex and the distance from the source to the current vertex.
    5. From the set of unvisited vertices, arbitrarily set one as the new current vertex, provided that there exists an edge to it such that it is the minimum of all edges from a vertex in the set of visited vertices to a vertex in the set of unvisited vertices. To reiterate: The new current vertex must be unvisited and have a minimum weight edges from a visited vertex to it. This can be done trivially by looping through all visited vertices and all adjacent unvisited vertices to those visited vertices, keeping the vertex with the minimum weight edge connecting it.
    6. Repeat steps 3-5 until all vertices are flagged as visited.

    Pseudocode

    								function Dijkstra(Graph, source):
    								dist[source] ← 0                           // Initialization
    								
    								create vertex set Q
    								
    								for each vertex v in Graph:           
    								if vsource
    								dist[v] ← INFINITY                 // Unknown distance from source to v
    								prev[v] ← UNDEFINED                    // Predecessor of v
    								
    								Q.add_with_priority(v, dist[v])
    								
    								
    								while Q is not empty:                      // The main loop
    								uQ.extract_min()                    // Remove and return best vertex
    								for each neighbor v of u:       // only v that are still in Q
    								alt ← dist[u] + length(u, v) 
    								if alt < dist[v]
    								dist[v] ← alt
    								prev[v] ← u
    								Q.decrease_priority(v, alt)
    								
    								return dist, prev
    							

    Demonstration for Dijkstra’s Algorithm

    Interactive module for Demonstrating Dijkstra Algorithm

    A Demonstration module which helps the learner to visualize the Dijkstra’s Algorithm on a graph.
    Learner can go step by step from the start node towards the end node. making a choice at every node along the way.
    Also gives them an insight for the calculation of time and space complexity of the traversal.

    Practice for Dijkstra’s Algorithm

    Interactive module for Practicing Dijkstra’s Algorithm

    A practice module

    Exercise for Dijkstra’s Algorithm

    Exercise for Dijkstra’s Algorithm

    An Exercise module.

    A Quiz with Multiple Choice Questions

    Q1. Dijkstra’s algorithm cannot be applied on ____.

    (A) Directed and weighted graphs

    (B) Container of objects of similar types

    (C) Container of objects of mixed types

    (D) All of the mentioned

    An array is a data structure, which can store a fixed-size collection of elements of the same data type.

    Q2. Dijkstra’s Algorithm is the prime example for ________.

    (A) Greedy algorithm

    (B) Branch and bound

    (C) Back tracking

    (D) Dynamic programming

    Dijkstra’s Algorithm is the prime example for greedy algorithms because greedy algorithms generally solve a problem in stages by doing what appears to be the best thing at each stage.

    Q3. Given a directed graph where weight of every edge is same, we can efficiently find shortest path from a given source to destination using _______.

    (A) Dijkstra’s Shortest Path Algorithm

    (B) Neither Breadth First Traversal nor Dijkstra’s algorithm can be used

    (C) Depth First Search

    (D) Breadth First Traversal

    With Breadth First Search, we first find explore vertices at one edge distance, then all vertices at 2 edge distance, and so on.

    Q4. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by ________.

    (A) Dijkstra’s algorithm starting from S.

    (B) Warshall’s algorithm

    (C) Performing a DFS starting from S.

    (D) Performing a BFS starting from S.

    Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E)
    Time Comlexity of the Warshall’s algorithm is O(|V|^3)
    DFS cannot be used for finding shortest paths
    BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

    Q5. Which of the following algorithm can be used to efficiently calculate single source shortest paths in a Directed Acyclic Graph?

    (A) Dijkstra

    (B) Bellman-Ford

    (C) Topological Sort

    (D) Strongly Connected Component

    Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E)
    Time Comlexity of the Warshall’s algorithm is O(|V|^3)
    DFS cannot be used for finding shortest paths
    BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

    Analysis

    Estimated Time

    10 minutes

    Video for analyzing Dijkstra’s Algorithm

    A video which helps the learner to analyze the algorithm
    also calculation of time and space complexity of the operation.

    Learning Objectives of this Module:

    In this module, we will be learning about:

    • Time and Space complexity: We will learn about the running time of one iteration, and then extend it to N iterations to complete the sorting process.
    • Comparison with other algorithms: We will compare Bubble sort with other sorting algorithms and see in which situations Bubble sort is the optimal/not optimal approach to take.

    Time and Space Complexity of Dijkstra’s algorithm

    Running Time of Dijkstra’s algorithm

    The time complexity of the given code/algorithm looks O(V^2) as there are two nested while loops. If we take a closer look, we can observe that the statements in inner loop are executed O(V+E) times (similar to BFS). The inner loop has decreaseKey() operation which takes O(LogV) time. So overall time complexity is O(E+V)*O(LogV) which is O((E+V)*LogV) = O(ELogV) Note that the above code uses Binary Heap for Priority Queue implementation. Time complexity can be reduced to O(E + VLogV) using Fibonacci Heap. The reason is, Fibonacci Heap takes O(1) time for decrease-key operation while Binary Heap takes O(Logn) time.

    Best and Worst Cases for Dijkstra’s Algorithm

    • The worst case (where log denotes the binary logarithm log 2 ) for connected graphs this time bound can be simplified to Θ (|E|log⁡ |V|) . The Fibonacci heap improves this to O(|E| + |V| * log⁡ |V|).
    • When using binary heaps, the average case time complexity is lower than the worst-case: assuming edge costs are drawn independently from a common probability distribution, the expected number of decrease-key operations is bounded by O(|V| * log(|E| / |V|)), giving a total running time of O(|E| + |V| * log ⁡|E| / |V| * log⁡ |V|).

    Time complexity of Dijkstra’s Algorithm


    Learner can input a random number and then go step by step from the start node towards the correct location for all the nodes.
    Also gives them an insight for the calculation of time and space complexity of the operation.

    Space complexity of Dijkstra’s algorithm

    Space complexity of Dijkstra’s algorithm is O(V2) where V denotes the number of vertices (or nodes) in the graph.

    Comparison with other algorithms

    Graph: Time Complexities of Shortest path Algorithms

    A video which helps the learner to visualize the operation using the below interavtive module.
    also calculation of time and space complexity of the operation.

    Comparison with other algorithms

    There are mainly three other single source shortest path algorithms:

    • Bellman Ford: n 3
    • Floyd Warshal: n*e

    A Quiz with Multiple Choice Questions

    Q1. Which of the following statement(s)is / are correct regarding Bellman-Ford shortest path algorithm?
    P: Always finds a negative weighted cycle, if one exist s.
    Q: Finds whether any negative weighted cycle is reachable from the source.

    (A) P Only

    (B) Q Only

    (C) Both P and Q

    (D) All of the mentioned

    An array is a data structure, which can store a fixed-size collection of elements of the same data type.

    Q2. What is the time complexity of insertion at any point on an array?

    (A) O(N)

    (B) O(N^2)

    (C) O(NLogN)

    (D) None of these

    Taking a general example,inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array,you will need to move n elements

    Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

    (A) X will always be a better choice for small inputs

    (B) X will always be a better choice for large inputs

    (C) Y will always be a better choice for small inputs

    (D) X will always be a better choice for all inputs

    Performance could be similar for small inputs, but definitely better for larger inputs

    Q4. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by______.

    (A) Dijkstra’s algorithm starting from S.

    (B) Warshall’s algorithm

    (C) O(N + M) time, O(1) space

    (D) O(N * M) time, O(N + M) space

    The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.

    Post Test of the Experiment

    Estimated Time

    10 minutes

    Instructions for Quiz

    Post Test includes questions on entire experiment concepts. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

    A Quiz with Multiple Choice Questions

    Q1. Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is _____.

    (A) 4

    (B) 7

    (C) 23

    (D) 99

    The task is to find minimum number of edges in a path in G from vertex 1 to vertex 100 such that we can move to either i+1 or 3i from a vertex i.

    Q2. Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ∈ V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) – d(v)?

    (A) -1

    (B) 0

    (C) 1

    (D) 2

    Note that the given graph is undirected, so an edge (u, v) also means (v, u) is also an edge. Since a shorter path can always be obtained by using edge (u, v) or (v, u), the difference between d(u) and d(v) can not be more than 1.

    Q3. Consider a weighted undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always true?

    (A) weight (u, v) < 12

    (B) weight (u, v) ⩽ 12

    (C) weight (u, v) > 12

    (D) weight (u, v) ⩾ 12

    The minimum weight happens when (S,U) + (U,V) = (S,V) Else (S,U) + (U,V) >= (S,V) Given (S,U) = 53, (S,V) = 65 53 + (U,V) >= 63 (U,V) >= 12.

    Q4. What is the time complexity of Dijikstra’s algorithm?

    (A) O(N)

    (B) O(N3)

    (C) O(N2)

    (D) O(logN)

    Time complexity of Dijkstra’s algorithm is O(N2) because of the use of doubly nested for loops. It depends on how the Adjacency table is manipulated.

    Q5. Given a directed graph where weight of every edge is same, we can efficiently find shortest path from a given source to destination using _______.

    (A) Breadth First Traversal

    (B) Dijkstra's Shortest Path Algorithm

    (C) Neither Breadth First Traversal nor Dijkstra's algorithm can be used

    (D) Depth First Search

    With BFS, we first find explore vertices at one edge distance, then all vertices at 2 edge distance, and so on.

    Further Readings of the Experiment

    Explore More About Dijkstra’s algorithm

    You can explore more about Dijkstra’s shortest path algorithm Experiment through following resources:


    Animations

    Other resources

    Credits:

    Kenji Ikeda 2015 Thanks for giving us permission to use your js codes according to General Public Licence (GPL).