.png)
Mobiprep has created last-minute notes for all topics of Algorithm to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Algorithm.
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Shortest Path
Question- 1) Explain Single Source Shortest Paths in a directed acyclic graph?
Answer: A directed Acyclic graph is a graph with directed edges and no cycles. We can calculate single source shortest distances in O(V+E) time for Directed Acyclic Graphs where V is the number of nodes and E is the number of edges present in the graph. The idea is to use topological sorting.
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge ab, vertex a comes before b in the ordering.
Consider an example:
Consider the above diagram. The objective is to find the minimum distance between point A and H. To achieve this, we will use topological sorting.
∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
A | B | C | D | E | F | G | H |
Now start with A and explore all the possible nodes and choose the minimum edge weight node. Initially like from A we can explore B and C and among them B have the minimum weight edges so we will choose that.
0 | 3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
A | B | C | D | E | F | G | H |
Now we can observe that from B as well as from A we can explore c so we will choose minimum as A-C is 6 and A-B-C is 7 so we will choose c
0 | 3 | 6 | ∞ | ∞ | ∞ | ∞ | ∞ |
A | B | C | D | E | F | G | H |
Repeat the process until you reach the end point i.e. H
0 | 3 | 6 | 7 | ∞ | ∞ | ∞ | ∞ |
A | B | C | D | E | F | G | H |
0 | 3 | 6 | 7 | 3 | ∞ | ∞ | ∞ |
A | B | C | D | E | F | G | H |
0 | 3 | 6 | 7 | 3 | 12 | ∞ | ∞ |
A | B | C | D | E | F | G | H |
0 | 3 | 6 | 7 | 3 | 12 | 9 | ∞ |
A | B | C | D | E | F | G | H |
0 | 3 | 6 | 7 | 3 | 12 | 9 | 11 |
A | B | C | D | E | F | G | H |
So, the single source shortest paths between A and H in a directed acyclic graph give above is of weight 11.
i.e. A->B->D->G->H
Code implementation:
// C++ program to find single source shortest paths for Directed Acyclic Graphs
#include<iostream>
#include <bits/stdc++.h>
#define INF INT_MAX
usingnamespacestd;
// Graph is represented using adjacency list. Every node of adjacency list
// contains vertex number of the vertex to which edge connects. It also
// contains weight of the edge
classAdjListNode
{
intv;
intweight;
public:
AdjListNode(int_v, int_w) { v = _v; weight = _w;}
intgetV() { returnv; }
intgetWeight() { returnweight; }
};
// Class to represent a graph using adjacency list representation
classGraph
{
intV; // No. of vertices'
// Pointer to an array containing adjacency lists
list<AdjListNode> *adj;
// A function used by shortestPath
voidtopologicalSortUtil(intv, boolvisited[], stack<int>&Stack);
public:
Graph(intV); // Constructor
// function to add an edge to graph
voidaddEdge(intu, intv, intweight);
// Finds shortest paths from given source vertex
voidshortestPath(ints);
};
Graph::Graph(intV)
{
this->V = V;
adj = newlist<AdjListNode>[V];
}
voidGraph::addEdge(intu, intv, intweight)
{
AdjListNodenode(v, weight);
adj[u].push_back(node); // Add v to u's list
}
voidGraph::topologicalSortUtil(intv, boolvisited[], stack<int>&Stack)
{
// Mark the current node as visited
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<AdjListNode>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
AdjListNode node = *i;
if(!visited[node.getV()])
topologicalSortUtil(node.getV(), visited, Stack);
}
// Push current vertex to stack which stores topological sort
Stack.push(v);
}
// The function to find shortest paths from given vertex. It uses recursive
// topologicalSortUtil() to get topological sorting of given graph.
voidGraph::shortestPath(ints)
{
stack<int> Stack;
intdist[V];
// Mark all the vertices as not visited
bool*visited = newbool[V];
for(inti = 0; i< V; i++)
visited[i] = false;
// Call the recursive helper function to store Topological Sort
// starting from all vertices one by one
for(inti = 0; i< V; i++)
if(visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Initialize distances to all vertices as infinite and distance
// to source as 0
for(inti = 0; i< V; i++)
dist[i] = INF;
dist[s] = 0;
// Process vertices in topological order
while(Stack.empty() == false)
{
// Get the next vertex from topological order
intu = Stack.top();
Stack.pop();
// Update distances of all adjacent vertices
list<AdjListNode>::iterator i;
if(dist[u] != INF)
{
for(i = adj[u].begin(); i != adj[u].end(); ++i)
if(dist[i->getV()] >dist[u] + i->getWeight())
dist[i->getV()] = dist[u] + i->getWeight();
}
}
// Print the calculated shortest distances
for(inti = 0; i< V; i++)
(dist[i] == INF)? cout<< "INF ": cout<<dist[i] << " ";
}
// Driver program to test above functions
intmain()
{
// Create a graph given in the above diagram. Here vertex numbers are
// 0, 1, 2, 3, 4, 5 with following mappings:
// 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
Graph g(6);
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 3);
g.addEdge(1, 3, 6);
g.addEdge(1, 2, 2);
g.addEdge(2, 4, 4);
g.addEdge(2, 5, 2);
g.addEdge(2, 3, 7);
g.addEdge(3, 4, -1);
g.addEdge(4, 5, -2);
ints = 1;
cout<< "Following are shortest distances from source "<< s <<" n";
g.shortestPath(s);
return0;
}
Question- 2) Explain Negative Weight Edges ?
Answer: An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two (or in hypergraphs, more) vertices to which it is attached, called its endpoints. Edges may be directed or undirected, Positive or negative. Negative edges are used to represent deprivation or the negative aspect of a graph.
Negative edges represent loss in real world scenario.
Consider an example, a person visited multiple cities. The edges represent the profit or loss the person undergoes while visiting one city from another depending on various factors.
Consider the value of graph in thousands. From the above graph we can say that if the person travels from A to B he gets a profit of 8000 whereas if a person moves from G to C it suffers a loss of 1000.
So, we can say that negative edges signify something opposite to the natural meaning.
Question- 3) Explain Dijkstra's Algorithm? Advantages and Disadvantages.
Answer: Dijkstra's Algorithm is a shortest path algorithm used to find the shortest path from source to all the possible vertex present in the graph. The algorithm used greedy approach to solve this problem. It is one of the most efficient algorithms but is not efficient to deal with negative weighted graph
The time complexity for all V vertices is V * (E*logV) i.eO(VElogV).
Pseudo code :
Input: Graph G, source vertex s, w (the weight of the edge)
Output: Shortest distance between source s and destination
Notation:
G =Weighted directed graph
S= Set of vertices
w (u, v) = the weight of the edge between u and v
s=source vertex
DIJKSTRA (G, w, s)
Initialize-single source (G, s)
S=Φ
Q=G.V
While Q !=Φ
U=EXTRACT-MIN(Q)
S=S U {u}
for each vertex v € G.Adj[u]
RELAX(u,v,w)Consider the below graph:
We will be using Dijkstra's algorithm to find the shortest distance from vertex V1 to all other.
V1 | V2 | V3 | V4 | V5 | V6 |
0 | ∞ | ∞ | ∞ | ∞ | ∞ |
As our starting vertex is V1 so choose V1 and explore all the possible vertex that can be accessed through V1
V2 | V3 | V4 | V5 | V6 |
2 | 4 |