Advanced C with Data Structures
Study Materials
Shortest Path Algorithm:
• In C programming, finding the shortest path between nodes in a graph is a
common and crucial problem with applications in various fields such as
networking, transportation, and logistics.
• Shortest path algorithms are designed to find the most efficient route from a
starting node to a destination node, minimizing the total travel cost, which could
be in terms of distance, time, or any other metric.
Types of Shortest Path Algorithms:
• Shortest path algorithms can be categorized into two main types:
• Single Source Shortest Path Algorithms: These algorithms find the shortest paths
from a single source vertex to all other vertices in the graph.
• All Pair Shortest Path Algorithms: These algorithms find the shortest paths
between every pair of vertices in the graph.
Single Source Shortest Path Algorithms:
• Dijkstra’s Algorithm: Works for graphs with non-negative edge weights.
• Bellman-Ford Algorithm: Can handle graphs with negative edge weights.
• A*Search Algorithm: Uses heuristics to try to speed up the search.
• All Pair Shortest Path Algorithms:
• Floyd-Warshall Algorithm: Finds shortest paths between all pairs of vertices.
• Johnson’s Algorithm: Combines Dijkstra’s algorithm with Bellman-Ford to find all
pair shortest paths.
Comparison of Shortest Path Algorithms:
Dijkstra's Algorithm:
• Efficient for graphs with non-negative weights.
• Finds the shortest path between a source and all other vertices.
• Time complexity: O(V + E log V) where V is the number of vertices and E is the
number of edges.
• Used in real-time applications like Google Maps, routing protocols, etc..
Dijkstra’s algorithm:
• Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree.
• Like Prim’s MST, we generate an SPT (shortest path tree) with a given source as
the root.
• We maintain two sets, one set contains vertices included in the shortest path
tree, other set includes vertices not yet included in the shortest path tree.
• At every step of the algorithm, we find a vertex that is in the other set (set of not
yet included) and has a minimum distance from the source.
Complexity Analysis:
• Time Complexity: The time complexity of Dijkstra’s algorithm is O(V^2).
• This is because the algorithm uses two nested loops to traverse the graph and
find the shortest path from the source node to all other nodes.
• Space Complexity: The space complexity of Dijkstra’s algorithm is O(V), where V
is the number of vertices in the graph.
• This is because the algorithm uses an array of size V to store the distances from
the source node to all other nodes.
Steps:
• Start at the source vertex, assign it a distance of 0. Set all other vertices to
infinity.
• Use a priority queue to greedily choose the closest vertex.
• Update the shortest distances to neighboring vertices.
• Repeat until all vertices are processed.
Problem Statement:
• Given a weighted graph and a source vertex in the graph, find the shortest
paths from the source to all the other vertices in the given graph.
• The given graph does not contain any negative edge.
Problem Statement:
• Input: src = 0,
• Output: 0 4 12 19 21 11 9 8 14
• Explanation: The distance from 0 to 1 = 4.
• The minimum distance from 0 to 2 = 12. 0->1->2
• The minimum distance from 0 to 3 = 19. 0->1->2->3
• The minimum distance from 0 to 4 = 21. 0->7->6->5->4
• The minimum distance from 0 to 5 = 11. 0->7->6->5
• The minimum distance from 0 to 6 = 9. 0->7->6
• The minimum distance from 0 to 7 = 8. 0->7
• The minimum distance from 0 to 8 = 14. 0->1->2->8
Adjacency Matrix:
• The idea is to generate a SPT (shortest path tree) with a given source as a root.
Maintain an Adjacency Matrix with two sets,
• one set contains vertices included in the shortest-path tree,
• other set includes vertices not yet included in the shortest-path tree.
• At every step of the algorithm, find a vertex that is in the other set (set not yet
included) and has a minimum distance from the source.
Limitations of Dijkstra’s Algorithm:
• Does not work with negative weight edges.
• Not suited for graphs with dynamic edge weights.
• Less efficient for graphs with large numbers of vertices
• (scalable, but still has limits).
Applications:
• Navigation systems: Google Maps, GPS, etc.
• Telecommunication: Network routing protocols (e.g., OSPF).
• Transportation: Optimizing routes for shipping and delivery.
Advantages:
• Efficient for dense graphs with non-negative weights.
• Real-world applications: Network routing, shortest path finding in maps, etc.
• Can handle both directed and undirected graphs.
Minimum Spanning Tree:
• The algorithm starts with an empty spanning tree. The idea is to maintain two
sets of vertices.
• The first set contains the vertices already included in the MST, and the other set
contains the vertices not yet included.
• At every step, it considers all the edges that connect the two sets and picks the
minimum weight edge from these edges.
• After picking the edge, it moves the other endpoint of the edge to the set
containing MST.
Two Popular Algorithms for MST:
• Kruskal's Algorithm:
• Greedy algorithm.
• Sort edges by weight and add them to the MST, ensuring no cycles are formed.
• Prim's Algorithm:
• Greedy algorithm.
• Grows the MST from an arbitrary starting vertex by adding the smallest edge
connecting the tree to a new vertex.
Two Popular Algorithms for MST:
Steps:
• Step 1: Determine an arbitrary vertex as the starting vertex of the MST.
• Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST
(known as fringe vertex).
• Step 3: Find edges connecting any tree vertex with the fringe vertices.
• Step 4: Find the minimum among these edges.
• Step 5: Add the chosen edge to the MST if it does not form any cycle.
• Step 6: Return the MST and exit
Process:
Step 1:
• Step 1: Firstly, we select an arbitrary vertex that acts as the starting vertex of the
Minimum Spanning Tree. Here we have selected vertex 0 as the starting vertex.
Step 2:
• Step 2: All the edges connecting the incomplete MST and other vertices are the
edges {0, 1} and {0, 7}.
• Between these two the edge with minimum weight is {0, 1}. So include the edge
and vertex 1 in the MST.
Step 3:
• Step 3: The edges connecting the incomplete MST to other vertices are {0, 7}, {1,
7} and {1, 2}. Among these edges the minimum weight is 8 which is of the edges
{0, 7} and {1, 2}. Let us here include the edge {0, 7} and the vertex 7 in the MST.
[We could have also included edge {1, 2} and vertex 2 in the MST].
Step 4:
• Step 4: The edges that connect the incomplete MST with the fringe vertices are
{1, 2}, {7, 6} and {7, 8}. Add the edge {7, 6} and the vertex 6 in the MST as it has
the least weight.
Step 5:
• Step 5: The connecting edges now are {7, 8}, {1, 2}, {6, 8} and {6, 5}. Include edge
{6, 5} and vertex 5 in the MST as the edge has the minimum weight among them.
Step 6:
• Step 6: Among the current connecting edges, the edge {5, 2} has the minimum
weight. So include that edge and the vertex 2 in the MST.
Step 7:
• Step 7: The connecting edges between the incomplete MST and the other edges
are {2, 8}, {2, 3}, {5, 3} and {5, 4}. The edge with minimum weight is edge {2, 8}
which has weight 2. So include this edge and the vertex 8 in the MST.
Step 8:
• Step 8: See here that the edges {7, 8} and {2, 3} both have same weight which are
minimum. But 7 is already part of MST.
• So we will consider the edge {2, 3} and include that edge and vertex 3 in the MST.
Step 9:
• Step 9: Only the vertex 4 remains to be included. The minimum weighted edge
from the incomplete MST to 4 is {3, 4}.
Step 10:
• The final structure of the MST is as follows and the weight of the edges of the
MST is (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37.
MST Structure:
Real-World Applications of MST:
Computer Networks:
• Design of minimum cost network connections (Internet, LAN).
Transportation Networks:
• Optimal layout of roads, railways, or pipelines.
Image Processing:
• MSTs are used in segmentation and object recognition.
Cluster Analysis:
• MST helps in clustering in machine learning by grouping similar points.