top of page

## Algorithms Notes

Algorithm Basics

Divide And Conquer

Greedy Algorithm

Dynamic Programming

Shortest Path

Backtracking

Minimum Spanning Tree

Maximum Flow

Complexity Classes

Q

1

Explain Single Source Shortest Paths in a directed acyclic graph?

Ans

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
{
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

// A function used by shortestPath
voidtopologicalSortUtil(intv, boolvisited[], stack<int>&Stack);
public:
Graph(intV); // Constructor

// function to add an edge to graph

// Finds shortest paths from given source vertex
voidshortestPath(ints);
};

Graph::Graph(intV)
{
this->V = V;
}

{
}

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
{
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
if(dist[u] != INF)
{
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);

ints = 1;
cout<< "Following are shortest distances from source "<< s <<" n";
g.shortestPath(s);

return0;
}

Q

2

Explain Negative Weight Edges ?

Ans

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.

Q

3

Ans

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 âˆž âˆž âˆž

Now among these the smallest one is V2 so select V2. And explore all vertex and if it can relax any vertex with less value than replace that value. We can observe that V3 can be reached through v2 with total weight 2+1=3
V2 V3 V4 V5 V6
2 3 9 âˆž âˆž

Now select V2

V2 V3 V4 V5 V6
2 3 9 6 âˆž

Now Select the minimum in all unselected vertex.

V2 V3 V4 V5 V6
2 3 8 6 11
Now select V4

V2 V3 V4 V5 V6
2 3 8 6 11

Now select V4

V2 V3 V4 V5 V6
2 3 8 6 9

Now select 6

V2 V3 V4 V5 V6
2 3 8 6 9

So, the result is
Vertex Distance
V2 2
V3 3
V4 8
V5 6
V6 9

1) Implemented in many used applications like Google Maps.
2) It is used in finding Shortest Path.
3) To find locations of Map which refers to vertices of graph.
4) Distance between the location refers to edges.
5) It is used in IP routing to find Open shortest Path First.
6) It is used in the telephone network.
1) It does blind search so wastes lot of time while processing.
2) It cannot handle negative edges.
3) This leads to acyclic graphs and most often cannot obtain the right shortest path.

Code Implementation:

// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <limits.h>
#include <stdio.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
intminDistance(intdist[], boolsptSet[])
{
// Initialize min value
intmin = INT_MAX, min_index;

for(intv = 0; v < V; v++)
if(sptSet[v] == false&&dist[v] <= min)
min = dist[v], min_index = v;

returnmin_index;
}

// A utility function to print the constructed distance array
voidprintSolution(intdist[])
{
printf("Vertex \t\t Distance from Source\n");
for(inti = 0; i< V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
voiddijkstra(intgraph[V][V], intsrc)
{
intdist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i

boolsptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false
for(inti = 0; i< V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
for(intcount = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in the first iteration.
intu = minDistance(dist, sptSet);

// Mark the picked vertex as processed
sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.
for(intv = 0; v < V; v++)

// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from srcto v through u is
// smaller than current value of dist[v]
if(!sptSet[v] && graph[u][v] &&dist[u] != INT_MAX
&&dist[u] + graph[u][v] <dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array
printSolution(dist);
}

// driver program to test above function
intmain()
{
/* Let us create the example graph discussed above */
intgraph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return0;
}

Q

4

Explain Bellman-Ford Algorithm?

Ans

Bellman-Ford algorithm is another algorithm used to find the shortest distance from a source vertex to all the vertex present in the graph. Bellman-Ford algorithm is slower than Dijkstra algorithm but is considered as a versatile algorithm as it is capable of handling negative weighted graphs as well.
Pseudo code:
Input data:
graph with nodes V and arcs E with weights f(e);
source node u.
Output data:
distances d(v) from the source node u to each node v âˆˆV.

for eachvâˆˆVdod(v) := âˆž
d(u) = 0

forifrom 1 to |V| - 1:
for eache = (w, v) âˆˆE:
ifd(v) >d(w) + f(e):
d(v) := d(w) + f(e)

Consider the below diagram:
Applying Bellman-Ford algorithm
Step1:
Count the number of vertices in the graph:
Now as in the diagram we can see there are 7 vertices so for this problem every vertex will undergo maximum n-1 relaxation i.e. 7-1=6 relaxation.
Relaxation formula:
If(d[u]+c(u,v)<d[v ])
Then
d[v]= d[u]+c(u,v)
where d[u], d[v] is the weight quantity associated with vertex u and v, c(u,v) is the edge weight between vertex u and v.

Step 2:
Enlist all the edges
(1,2) (1,3) (1,4) (2,5) (3,2) (3,5) (4,3) (4,6) (5,7) (6,7)
Initially all vertices are marked as infinity so
V1 V2 V3 V4 V5 V6 V7
0 âˆž âˆž âˆž âˆž âˆž âˆž

Take the first pair (1,2):
So d[u]=d[V1]=0
c(u,v)=c(V1,V2)= 6 and d[v]=d[V1]=âˆž
Applying relaxation formula
d[u]+c(u,v)<d[v]) i.e. d[V1]+c(V1,V2)<d[V2])
0+6<âˆž so the condition satisfies hence replace d[v2] with d[V1]+c(V1,V2) so the table is

V1 V2 V3 V4 V5 V6 V7
0 6 âˆž âˆž âˆž âˆž âˆž

Now repeat the process for all the vertex taking the above table as the reference for updated value
V1 V2 V3 V4 V5 V6 V7
0 6 3 5 5 4 7

This entire process is counted as one relaxation. Now with the current table repeat the same process five more time to get the final result
2nd relaxation
Repeat the same process again
V1 V2 V3 V4 V5 V6 V7
0 1 3 5 2 4 5

3nd relaxation
V1 V2 V3 V4 V5 V6 V7
0 1 3 5 0 4 3

4th relaxation
V1 V2 V3 V4 V5 V6 V7
0 1 3 5 0 4 3

Now we can observe that 4th and 3rd relaxation are equal so we can stop here.
So, the shortest path of from source V1 to all vertices are

V1->V2=1
V1->V3=3
V1->V4=5
V1->V5=0
V1->V6=4
V1->V7=3

Code Implementation

// A C++ program for Bellman-Ford's single source
// shortest path algorithm.
#include <bits/stdc++.h>

// a structure to represent a weighted edge in graph
structEdge {
intsrc, dest, weight;
};

// a structure to represent a connected, directed and
// weighted graph
structGraph {
// V-> Number of vertices, E-> Number of edges
intV, E;

// graph is represented as an array of edges.
structEdge* edge;
};

// Creates a graph with V vertices and E edges
structGraph* createGraph(intV, intE)
{
structGraph* graph = newGraph;
graph->V = V;
graph->E = E;
graph->edge = newEdge[E];
returngraph;
}

// A utility function used to print the solution
voidprintArr(intdist[], intn)
{
printf("Vertex Distance from Source\n");
for(inti = 0; i< n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}

// The main function that finds shortest distances from src to
// all other vertices using Bellman-Ford algorithm. The function
// also detects negative weight cycle
voidBellmanFord(structGraph* graph, intsrc)
{
intV = graph->V;
intE = graph->E;
intdist[V];

// Step 1: Initialize distances from src to all other vertices
// as INFINITE
for(inti = 0; i< V; i++)
dist[i] = INT_MAX;
dist[src] = 0;

// Step 2: Relax all edges |V| - 1 times. A simple shortest
// path from src to any other vertex can have at-most |V| - 1
// edges
for(inti = 1; i<= V - 1; i++) {
for(intj = 0; j < E; j++) {
intu = graph->edge[j].src;
intv = graph->edge[j].dest;
intweight = graph->edge[j].weight;
if(dist[u] != INT_MAX &&dist[u] + weight <dist[v])
dist[v] = dist[u] + weight;
}
}

// Step 3: check for negative-weight cycles. The above step
// guarantees shortest distances if graph doesn't contain
// negative weight cycle. If we get a shorter path, then there
// is a cycle.
for(inti = 0; i< E; i++) {
intu = graph->edge[i].src;
intv = graph->edge[i].dest;
intweight = graph->edge[i].weight;
if(dist[u] != INT_MAX &&dist[u] + weight <dist[v]) {
printf("Graph contains negative weight cycle");
return; // If negative cycle is detected, simply return
}
}

printArr(dist, V);

return;
}

// Driver program to test above functions
intmain()
{
/* Let us create the graph given in above example */
intV = 5; // Number of vertices in graph
intE = 8; // Number of edges in graph
structGraph* graph = createGraph(V, E);

// add edge 0-1 (or A-B in above figure)
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;

// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;

// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;

// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;

// add edge 1-4 (or A-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;

// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;

// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;

// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;

BellmanFord(graph, 0);

return0;
}

Q

5

Explain All-Pairs Shortest Paths

Ans

All pair shortest path algorithms are the algorithms that are used to find the shortest distance between all the vertices present within the graph.
There are many all-pairs shortest path algorithms like Johnson's algorithm, Floyd-Warshall algorithm with efficiency in different scenario
Floyd-Warshall algorithm is efficient in dealing with graphs which have all positive weighted graph.
Johnson's algorithm is less efficient than Floyd-Warshall algorithm but it is considered as a versatile algorithm as it can provide result in case of negative weighted graph as well.

Q

6

Explain Floyd-Warshall Algorithm.

Ans

Floyd-Warshall Algorithm is one of the shortest path algorithms used to calculate the shortest path between all pairs of vertices present in the graph. This algorithm works on the dynamic programming approach and is helpful is finding shortest path in a weighted graph with positive as well as negative weights (but with no negative cycles).
The time complexity of this algorithm is O(n3).
Pseudocode:
for i = 1 to N
for j = 1 to N
if there is an edge from i to j
dist[0][i][j] = the length of the edge from i to j
else
dist[0][i][j] = INFINITY

for k = 1 to N
for i = 1 to N
for j = 1 to N
dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])

Example:

Step 1: Create a matrix D(0) which represent all the weights between all the edges

D(0)= 0171026 âˆž 0

Now consider every vertex as an intermediate node
Consider Vertex 1 as intermediate:
Possible Path: (2-1-3), (3-1-2)
D1(2,3) =min{D0(2,3), D0(2,1) +D0(1,3)}
=min {2,1+7}
=2 i.e., remains unchanged
D1(3,2) =min{D0(3,2), D0(3,1) +D0(1,2)}
=min {âˆž, 6+4}
=10
10<âˆž. Hence the previous entry of âˆž for 3rd row and 2nd column is replaced by 10.

D (1) = 0471026100

Consider Vertex 2 as intermediate:
Possible Path: (1-2-3)
D2(1,3) =min{D1(1,3), D1(1,2) +D1(2,3)}
=min {7, 4+2}
=6
6<7. Hence the previous entry of 7 for 1st row and 3rd column is replaced by 6.

D (2) =0461026100

Consider Vertex 3 as intermediate:
Possible path: (2-3-1)
D3(2,1) =min{D2(2,1), D2(2,3) +D2(3,1)}
=min {1,2+6}
=1
i.e., remains unchanged

D (3) = 0461026100
D (3) gives shortest distances between any pair of vertices
Code snippet:
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
int dist[N][N]; // For some N

void calculate_all_pairs_shortest_path() {
int i, j, k;
for ( k = 0; k < N; k++ )
for ( i = 0; i< N; i++ )
for ( j = 0; j < N; j++ )
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );
}

int get_distance(int u, int v) {
return dist[u][v];
}

Q

7

Explain Johnson's Algorithm?

Ans

Johnson's algorithm is another algorithm that can be used to find the shortest distance between all pairs of vertices in a graph. The algorithm is capable of dealing with negative weighted edges as well but the have the limitation that no negative weight cycle may exist.
The algorithm uses Bellman-Ford Algorithm to convert all the negative edges to positive and then apply Dijkstra algorithm to find the minimum distance between all possible pair.
Using Johnson's algorithm, we can find all pair shortest paths in O (V2log V + VE) time . Where V is the number of vertices and E is the number of edges present in the graph.
Pseudo code:
Input: Graph G
Output: List of all pair shortest paths for G

Notation:
G=graph
G'=new graph
W= original weight function.
s=new vertex
v=current vertex

Code Implementation

#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <exception>
#include <set>

using namespace std;

struct Edge {

long cost;
};

using Graph = vector<vector<Edge>>;
using SingleSP = vector<long>;
using AllSP = vector<vector<long>>;

const long INF = LONG_MAX;

// first line is in the format <N><M> where N is the number of vertices, M is the number of edges that follow

// each following line represents a directed edge in the form <Source><Dest><Cost>

Graph g;

int n, m;

is >> n >> m;

cout<< "Graph has " << n << " vertices and " << m << " edges." <<endl;

g.resize(n+1);

while (is) {

int v1, v2, c;

is >> v1 >> v2 >> c;

if (is) {

g[v1].push_back({v2, c});

}

}

return g;

}

// add a zero-cost edge from vertex 0 to all other edges

for (int i = 1; i<g.size(); i++) {

g[0].push_back({i, 0});

}

return g;

}

SingleSPbellmanford(Graph &g, int s) {

vector<vector<long>> memo(g.size()+2, vector<long>(g.size(), INF));

// initialise base case

memo[0][s] = 0;

for (int i = 1; i<memo.size(); i++) {

// compute shortest paths from s to all vertices, with max hop-count i

for (int n = 0; n <g.size(); n++) {

if (memo[i-1][n] < memo[i][n]) {

memo[i][n] = memo[i-1][n];

}

for (auto&e : g[n]) {

if (memo[i-1][n] != INF) {

if (memo[i-1][n] + e.cost< memo[i][e.head]) {

}

}

}

}

}

// check if the last iteration differed from the 2nd-last

for (int j = 0; j <g.size(); j++) {

if (memo[g.size()+1][j] != memo[g.size()][j]) {

throw string{"negative cycle found"};

}

}

return memo[g.size()];

}

SingleSPdjikstra(const Graph& g, int s) {

SingleSPdist(g.size(), INF);

set<pair<int,long>> frontier;

frontier.insert({0,s});

while (!frontier.empty()) {

pair<int,long> p = *frontier.begin();

frontier.erase(frontier.begin());

int d = p.first;

int n = p.second;

// this is our shortest path to n

dist[n] = d;

// now look at all edges out from n to update the frontier

for (auto e : g[n]) {

// update this node in the frontier if we have a shorter path

// we've seen this node before, so erase it from the set in order to update it

}

}

}

}

return dist;

}

AllSPjohnson(Graph &g) {

// now build "g prime" which is g with a new edge added from vertex 0 to all other edges, with cost 0

// now run Bellman-Ford to get single-source shortest paths from s to all other vertices

SingleSPssp;

try {

ssp = bellmanford(gprime, 0);

} catch (string e) {

cout<< "Negative cycles found in graph. Cannot compute shortest paths." <<endl;

throw e;

}
// no re-weight each edge (u,v) in g to be: cost + ssp[u] - ssp[v].

for (int i = 1; i<g.size(); i++) {

for (auto &e : g[i]) {

e.cost = e.cost + ssp[i] - ssp[e.head];

}

}
// now that we've re-weighted our graph, we can invoke N iterations of Djikstra to find

// all pairs shortest paths

AllSPallsp(g.size());

for (int i = 1; i<g.size(); i++) {

allsp[i] = djikstra(g, i);

}

// now re-weight the path costs back to their original weightings

for (int u = 1; u <g.size(); u++) {

for (int v = 1; v <g.size(); v++) {

if (allsp[u][v] != INF) {

allsp[u][v] += ssp[v] - ssp[u];

}

}

}

return allsp;

bottom of page