Minimum length paths between 1 to N including each node

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

In this article, we discuss how to find the minimum length paths from node 1 to node N including, each node. You can brush up on your knowledge of Graph and Queue by solving this problem. 

Problem Statement

Given an undirected graph with some nodes and edges, find the minimum length of the paths from the first node to the last node passing through every possible node. If no such path exists, return -1.

Example and Explanation

Consider the given graph.

Sample Input = int edgeList[][] = { {1, 2 }, {1, 4 }, {1, 5}, {2, 3 }, {2, 4}, {3, 4 }, {3, 5}, {4, 5} }

Expected Output = 1 3 3 2 1 

Explanation: 

The minimum path length from node 1 to node 5 passing through node 1 is 1 (1 -> 5).

The minimum path length from node 1 to node 5 passing through node 2 is 3 (1 -> 2 -> 4 -> 5 or 1-> 2 -> 3 -> 5).

The minimum path length from node 1 to node 5 passing through node 3 is 3 (1 -> 4 -> 3 -> 5). 

Approach

To solve the given problem, we will be performing Breadth-First Search(BFS) twice. 

Once from node 1 to the last node and then again from the last node to the first node. 

While performing the BFS traversal, we will be maintaining two arrays to store the minimum distance. Finally, the sum of the two arrays will be the required min-path.

The step-by-step implementation is as follows:

  • Create an array (say edge) that will store the edges for each node.
  • Create the two queues (say bfs1 and bfs2) that will store the nodes while performing the BFS traversal.
  • Push the first node in bfs1 and the last node in bfs2.
  • Create two arrays (say minDistF and minDistB) that will store the length of the minimum paths while performing BFS.
  • Set the value at minDistF[0] and minDistB[n-1] to 0, as the minimum distance path from one node to the same node is zero.
  • Perform BFS on the two queues separately. 
    For each BFS, traverse as long as the queue is not empty and:
    • Pop a node from the queue. Store the node (say node) and its distance (say dist).
    • If the current distance (that is dist) is greater than the stored minimum distance (that is value stored at minDistF[node] or minDistB[node]), continue.
    • Else traverse the given edge list for each child node for the parent node, node.
      • If the distance stored at minDist[y] is greater than dist+1 then, change minDist[y] to dist+1.
        This means that if the current path length (inclusive of the start node) is less than the stored path length, then update the minDist array.
  • The internal steps for both the BFS are the same.
  • Once both the BFS traversals are complete, iterate from 0 up to N and:
    • Check if minDistF[i] + minDistB[i] is greater than infinity or not.
    • If true, then print -1. This denotes that there exists no path between 1 to N.
    • If false then print the value of minDistF[i] + minDistB[i]. This denotes that there exists a path from node 1 to node N.

C++ implementation

#include<iostream>
#include<queue>
using namespace std;
#define ll long long int

void calcMinDist(int start, int end, int edgeList[][3])
{
    vector<ll> edge[100];

    for (int i = 0; i < end; i++) {
        int temp1 = edgeList[i][0] - 1;
        int temp2 = edgeList[i][1] - 1;
        edge[temp1].push_back(temp2);
        edge[temp2].push_back(temp1);
    }

    queue<pair<ll, ll> > bfs1;
    bfs1.push({ 0, 0 });
    vector<int> minDistF(start, INT32_MAX);
    minDistF[0] = 0;

    while (!bfs1.empty()) {
        auto up = bfs1.front();

        bfs1.pop();
        int x = up.first;
        int lev = up.second;
        if (lev > minDistF[x])
            continue;
        if (x == start - 1)
            continue;

        for (ll y : edge[x]) {
            if (minDistF[y] > lev + 1) {
                minDistF[y] = lev + 1;
                bfs1.push({ y, lev + 1 });
            }
        }
    }

    queue<pair<ll, ll> > bfs2;
    bfs2.push({ start - 1, 0 });
    vector<int> minDistB(start, INT32_MAX);
    minDistB[start - 1] = 0;

    while (!bfs2.empty()) {
        auto up = bfs2.front();

        bfs2.pop();
        int x = up.first;
        int lev = up.second;
        if (lev > minDistB[x])
            continue;
        if (x == 0)
            continue;

        for (ll y : edge[x]) {
            if (minDistB[y] > lev + 1) {
                minDistB[y] = lev + 1;
                bfs2.push({ y, lev + 1 });
            }
        }
    }

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

        if (minDistF[i] + minDistB[i] > INT32_MAX)
            cout << -1 << " ";

        else
            cout << "Minimum distance from Node 1 to Node " << (start) << " passing through Node " << (i+1) << " is: " << minDistF[i] + minDistB[i] << endl;
    }
}

int main()
{
    int nodes = 5;
    int edges = 8;
    int edgeList[edges][3] = {  { 1, 2 }, { 1, 4 },  {1, 5},
                                { 2, 3 }, { 2, 4},
                                { 3, 4 }, { 3, 5},
                                { 4, 5},
                            };

    calcMinDist(nodes, edges, edgeList);

    return 0;
}

 

OUTPUT

Minimum distance from Node 1 to Node 5 passing through Node 1 is: 1        
Minimum distance from Node 1 to Node 5 passing through Node 2 is: 3        
Minimum distance from Node 1 to Node 5 passing through Node 3 is: 3        
Minimum distance from Node 1 to Node 5 passing through Node 4 is: 2        
Minimum distance from Node 1 to Node 5 passing through Node 5 is: 1

Complexities

Time Complexity

In the given implementation, we perform BFS on the given graph. Thus the time complexity is,

T(n) = O(V+E),

where V is the number of vertices/nodes and E is the total number of edges.

Space Complexity

In the given implementation, we perform BFS and use a queue to store the nodes. Thus,

Space complexity = O(V),

where V is the number of vertices/nodes in one level.

Frequently Asked Questions

  1. What is BFS?
    Breadth First Search(BFS) is a graph traversal technique in which all the nodes of the same level are explored first before exploring the nodes of the lower level. Its pair is Depth First Search(DFS), where we traverse as low as possible in a single node before exploring the other nodes. To learn more about BFS and DFS visit, Traversal
     
  2. What is a Queue?
    A Queue is a which follows the First In First Out (FIFO) concept. The major operations on a queue are push() and pop(). To know more about queues visit, Queue.  

Key Takeaways

To summarize the article, we learned how to find minimum length paths between 1 to N, including each node. We saw the problem statement, an example, and the explanation. We also saw the approach and the C++ implementation along with the time and space complexity. To sum up the article, we discussed a few FAQs.

Want to learn more about Graph Traversals? Visit Graph Traversal to read many informative articles on the same.

Want to learn about topics like Web Technologies, Programing Fundamentals, Aptitude, DSA, and much more? Visit CN Library | Free Online Coding Resources today. 


Happy Coding!

Was this article helpful ?
0 upvotes