1 hour
Introduction video for Dijkstra’s Algorithm
This experiment requires you to have basic knowledge about :
In this experiment on Dijkstra's Shortest Path algorithm, you will learn following:
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 |
20 minutes
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:
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:
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.
30 minutes
Video giving a brief overview of Dijkstra’s Algorithm
In this module, we will learn about:
Let's take note of other single source shortest path algorithms and their Applications:
Dijkstra’s algorithm is used when the graph has positive weights only. It is faster than the above other single source shortest path algorithms.
Video for Dijkstra's Algorithm
function Dijkstra(Graph, source): dist[source] ← 0 // Initialization create vertex set Q for each vertex v in Graph: if v ≠ source 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 u ← Q.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
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.
A practice module
An Exercise module.
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|)
10 minutes
A video which helps the learner to analyze the algorithm
also calculation of time and space complexity of the operation.
In this module, we will be learning about:
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.
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 is O(V^{2}) where V denotes the number of vertices (or nodes) in the graph.
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.
There are mainly three other single source shortest path algorithms:
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.
10 minutes
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.
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(N^{3})
(C) O(N^{2})
(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.
You can explore more about Dijkstra’s shortest path algorithm Experiment through following resources: