Shortest Path in Directed Acyclic Graph in DSA C++ | DSA in C++ - Software Development PDF Download

Introduction

In the field of computer science, graphs are a fundamental data structure used to represent connections between various entities. A directed acyclic graph (DAG) is a special type of graph where edges have a specific direction, and it does not contain any cycles. Finding the shortest path in a DAG is a common problem with numerous real-world applications. In this article, we will explore the concept of finding the shortest path in a DAG and implement it using Dijkstra's algorithm.

What is a Directed Acyclic Graph (DAG)?

A directed acyclic graph (DAG) is a graph that contains directed edges between nodes but does not have any cycles. In simpler terms, it means that you cannot start from a node and follow the directed edges to return back to the same node without repeating any edges.

Dijkstra's Algorithm

Dijkstra's algorithm is a well-known graph traversal algorithm used to find the shortest path from a source node to all other nodes in a graph. It guarantees the shortest path when all edge weights are non-negative. Dijkstra's algorithm iteratively explores the nodes in the graph, updating the minimum distance to each node until it reaches the target node or all reachable nodes have been visited.

Implementing Shortest Path in a DAG using Dijkstra's Algorithm

To find the shortest path in a DAG using Dijkstra's algorithm, we need to perform a topological sort of the DAG to ensure that we visit the nodes in the correct order. Once the topological sort is done, we can apply Dijkstra's algorithm to compute the shortest path.

Here are the steps to implement the shortest path in a DAG using Dijkstra's algorithm:

• Perform a topological sort of the DAG.
• Initialize the distance to all nodes as infinity, except the source node which is set to 0.
• Traverse the nodes in the topologically sorted order.
• For each node, update the distance of its adjacent nodes if a shorter path is found.
• Repeat step 4 until all nodes have been visited.

Examples and Code Walkthrough

Let's consider a DAG with the following nodes and edges:

Nodes: A, B, C, D, E

Edges: (A -> B, weight = 3), (A -> C, weight = 6), (B -> D, weight = 1), (C -> D, weight = 2), (D -> E, weight = 4)

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

const int INF = INT_MAX;

// Structure to represent a node in the graph

struct Node {

    int id;

    int distance;

};

// Function to perform topological sort

void topologicalSort(vector<vector<pair<int, int>>>& graph, vector<bool>& visited, int node, stack<int>& result) {

    visited[node] = true;    

    for (auto neighbor : graph[node]) {

        if (!visited[neighbor.first]) {

            topologicalSort(graph, visited, neighbor.first, result);

        }

    }    

    result.push(node);

}

// Function to find the shortest path in a DAG using Dijkstra's algorithm

void shortestPathDAG(vector<vector<pair<int, int>>>& graph, int source) {

    int n = graph.size();

    vector<int> distance(n, INF);

    vector<bool> visited(n, false);

    stack<int> topologicalOrder;    

    // Perform topological sort

    for (int i = 0; i < n; i++) {

        if (!visited[i]) {

            topologicalSort(graph, visited, i, topologicalOrder);

        }

    }    

    // Set distance of source node to 0

    distance[source] = 0;    

    // Process nodes in topologically sorted order

    while (!topologicalOrder.empty()) {

        int node = topologicalOrder.top();

        topologicalOrder.pop();        

        // Update the distance of neighboring nodes

        if (distance[node] != INF) {

            for (auto neighbor : graph[node]) {

                int adjNode = neighbor.first;

                int weight = neighbor.second;          

                if (distance[node] + weight < distance[adjNode]) {

                    distance[adjNode] = distance[node] + weight;

                }

            }

        }

    }    

    // Print the shortest distances

    cout << "Shortest distances from node " << source << ":\n";

    for (int i = 0; i < n; i++) {

        if (distance[i] == INF) {

            cout << "Node " << i << ": Not reachable\n";

        } else {

            cout << "Node " << i << ": " << distance[i] << "\n";

        }

    }

}

int main() {

    int n = 5; // Number of nodes in the graph

    vector<vector<pair<int, int>>> graph(n);   

    // Add edges to the graph

    graph[0].push_back({1, 3});

    graph[0].push_back({2, 6});

    graph[1].push_back({3, 1});

    graph[2].push_back({3, 2});

    graph[3].push_back({4, 4});    

    int source = 0; // Source node    

    shortestPathDAG(graph, source);

    return 0;

}

Output:

Shortest distances from node 0:

Node 0: 0

Node 1: 3

Node 2: 6

Node 3: 4

Node 4: 8

Sample Problems and Solutions

Here are a few sample problems to practice finding the shortest path in a DAG:

Problem 1: Consider the following DAG. Find the shortest path from node 0 to node 4.

Nodes: 0, 1, 2, 3, 4

Edges: (0 -> 1, weight = 5), (0 -> 2, weight = 3), (1 -> 3, weight = 2), (2 -> 3, weight = 4), (3 -> 4, weight = 6)

Applying Dijkstra's algorithm, the shortest path from node 0 to node 4 is: 0 -> 1 -> 3 -> 4 with a total weight of 13.

Problem 2: Consider a DAG with nodes 0, 1, 2, 3, 4, and 5. Find the shortest path from node 2 to node 5.

Nodes: 0, 1, 2, 3, 4, 5

Edges: (0 -> 1, weight = 2), (0 -> 3, weight = 6), (1 -> 3, weight = 3), (1 -> 4, weight = 1), (2 -> 4, weight = 4), (2 -> 5, weight = 2), (3 -> 5, weight = 1), (4 -> 5, weight = 2)

Applying Dijkstra's algorithm, the shortest path from node 2 to node 5 is: 2 -> 5 with a total weight of 2.

Conclusion

Finding the shortest path in a directed acyclic graph (DAG) is a common problem in computer science. By utilizing Dijkstra's algorithm and performing a topological sort, we can efficiently compute the shortest path in a DAG. The provided examples and code should help you understand the concept and implement it in your own programs.