lOMoARcPSD|44613495
Advance Data Structures Module 4 Notes
Data Structure and Algorithms for Problem solving (Visvesvaraya Technological
University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Samuel Wachira ndiang'ui ()
, lOMoARcPSD|44613495
Data Structures & Algorithms for Problem Solving
Module – 4
Graph Algorithms and Polynomials with FFT
1. Graph Algorithms
Bellman-Ford Algorithm
Definition: The Bellman-Ford algorithm is a graph algorithm that computes the shortest
paths from a single source vertex to all other vertices in a weighted graph. It can handle
graphs with negative weight edges.
Algorithm Steps:
1. Initialize the distance to the source vertex as 0 and all other vertices as infinity.
2. For each vertex, relax all edges. This means for each edge ( (u, v) ) with weight ( w ), if
( distance[u] + w < distance[v] ), update ( distance[v] ).
3. Repeat the relaxation process for ( V-1 ) times, where ( V ) is the number of vertices.
4. Check for negative weight cycles by performing one more relaxation. If any distance
can still be updated, a negative cycle exists.
Complexity:
Time Complexity: (O(V \cdot E)), where (V) is the number of vertices and (E) is the
number of edges.
Space Complexity: (O(V)) for storing distances.
Single Source Shortest Paths in a DAG
Definition: In a Directed Acyclic Graph (DAG), the shortest paths from a single source can be
found using topological sorting.
Algorithm Steps:
1. Perform a topological sort of the DAG.
Downloaded by Samuel Wachira ndiang'ui ()
, lOMoARcPSD|44613495
2. Initialize the distance to the source vertex as 0 and all other vertices as infinity.
3. Process each vertex in topological order:
For each outgoing edge ( (u, v) ) with weight ( w ), if ( distance[u] + w <
distance[v] ), update ( distance[v] ).
Complexity:
Time Complexity: (O(V + E)) due to topological sorting and relaxation.
Space Complexity: (O(V)) for storing distances.
Johnson’s Algorithm for Sparse Graphs
Definition: Johnson’s algorithm finds the shortest paths between all pairs of vertices in a
sparse graph, even with negative weights, but without negative cycles.
Algorithm Steps:
1. Add a new vertex ( q ) connected to all other vertices with zero-weight edges.
2. Use the Bellman-Ford algorithm to find the shortest paths from ( q ) to all other
vertices. If a negative cycle is detected, terminate.
3. Reweight the edges using the formula: ( w'(u, v) = w(u, v) + h[u] - h[v] ), where ( h ) is
the distance from ( q ).
4. Use Dijkstra’s algorithm for each vertex to find the shortest paths in the reweighted
graph.
Complexity:
Time Complexity: (O(V^2 \log V + V E)) for sparse graphs.
Space Complexity: (O(V + E)).
Flow Networks and Ford-Fulkerson Method
Definition: The Ford-Fulkerson method computes the maximum flow in a flow network using
augmenting paths.
Algorithm Steps:
1. Initialize the flow in all edges to 0.
2. While there exists an augmenting path from the source to the sink, increase the flow
along this path.
Downloaded by Samuel Wachira ndiang'ui ()
Advance Data Structures Module 4 Notes
Data Structure and Algorithms for Problem solving (Visvesvaraya Technological
University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Samuel Wachira ndiang'ui ()
, lOMoARcPSD|44613495
Data Structures & Algorithms for Problem Solving
Module – 4
Graph Algorithms and Polynomials with FFT
1. Graph Algorithms
Bellman-Ford Algorithm
Definition: The Bellman-Ford algorithm is a graph algorithm that computes the shortest
paths from a single source vertex to all other vertices in a weighted graph. It can handle
graphs with negative weight edges.
Algorithm Steps:
1. Initialize the distance to the source vertex as 0 and all other vertices as infinity.
2. For each vertex, relax all edges. This means for each edge ( (u, v) ) with weight ( w ), if
( distance[u] + w < distance[v] ), update ( distance[v] ).
3. Repeat the relaxation process for ( V-1 ) times, where ( V ) is the number of vertices.
4. Check for negative weight cycles by performing one more relaxation. If any distance
can still be updated, a negative cycle exists.
Complexity:
Time Complexity: (O(V \cdot E)), where (V) is the number of vertices and (E) is the
number of edges.
Space Complexity: (O(V)) for storing distances.
Single Source Shortest Paths in a DAG
Definition: In a Directed Acyclic Graph (DAG), the shortest paths from a single source can be
found using topological sorting.
Algorithm Steps:
1. Perform a topological sort of the DAG.
Downloaded by Samuel Wachira ndiang'ui ()
, lOMoARcPSD|44613495
2. Initialize the distance to the source vertex as 0 and all other vertices as infinity.
3. Process each vertex in topological order:
For each outgoing edge ( (u, v) ) with weight ( w ), if ( distance[u] + w <
distance[v] ), update ( distance[v] ).
Complexity:
Time Complexity: (O(V + E)) due to topological sorting and relaxation.
Space Complexity: (O(V)) for storing distances.
Johnson’s Algorithm for Sparse Graphs
Definition: Johnson’s algorithm finds the shortest paths between all pairs of vertices in a
sparse graph, even with negative weights, but without negative cycles.
Algorithm Steps:
1. Add a new vertex ( q ) connected to all other vertices with zero-weight edges.
2. Use the Bellman-Ford algorithm to find the shortest paths from ( q ) to all other
vertices. If a negative cycle is detected, terminate.
3. Reweight the edges using the formula: ( w'(u, v) = w(u, v) + h[u] - h[v] ), where ( h ) is
the distance from ( q ).
4. Use Dijkstra’s algorithm for each vertex to find the shortest paths in the reweighted
graph.
Complexity:
Time Complexity: (O(V^2 \log V + V E)) for sparse graphs.
Space Complexity: (O(V + E)).
Flow Networks and Ford-Fulkerson Method
Definition: The Ford-Fulkerson method computes the maximum flow in a flow network using
augmenting paths.
Algorithm Steps:
1. Initialize the flow in all edges to 0.
2. While there exists an augmenting path from the source to the sink, increase the flow
along this path.
Downloaded by Samuel Wachira ndiang'ui ()
