Check if given path between two nodes of a graph represents a shortest paths

0 0 6 minutes read

Given an unweighted directed graph and Q queries consisting of sequences of traversal between two nodes of the graph, the task is to find out if the sequences represent one of the shortest paths between the two nodes.
Examples:

Input: 1 2 3 4
Output: NO

Explanation:
The first and last node of the input sequence 
is 1 and 4 respectively. The shortest path 
between 1 and 4 is 1 -> 3 -> 4 hence, 
the output is NO for the 1st example.

Input: 1 3 4
Output: YES

Approach:
The idea is to use Floyd Warshall Algorithm to store the length of all pairs of vertices. If the length of the shortest path between the starting and ending node of the sequence is one less than the length of the sequence, then the given sequence represents one of the shortest paths between the nodes.
Below is the implementation of above approach:

C++

// C++ program for 
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define INFINITE 10000
 
// Function to store the 
// length of shortest path 
// between all pairs of nodes
void shortestPathLength(int n, int graph[4][4], int dis[4][4])
{
  // Initializing dis matrix 
  // with current distance value  
  for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          dis[i][j] = graph[i][j];
      }
  }
 
  // Floyd-Warshall Algorithm
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
}
 
// A function that prints YES if the
// given path is the shortest path
// and prints NO if the given path
// is not shortest
void checkShortestPath(int length, int path[], int dis[4][4])
{
  // Check if the given path
  // is shortest or not
  // as discussed in above approach
  if (dis[path[0] - 1][path[length - 1] - 1] == length - 1) {
      cout << "YES" << endl;
  }
  else {
      cout << "NO" << endl;
  }
}
 
// Driver code
int main()
{
    // Adjacency matrix representing the graph
    const int n = 4;
    int graph[n][n] = { { 0, 1, 1, INFINITE },
                        { INFINITE, 0, 1, INFINITE },
                        { INFINITE, INFINITE, 0, 1 },
                        { 1, INFINITE, INFINITE, 0 } };
    // A matrix to store the length of shortest
    int dis[n][n];
 
    // path between all pairs of vertices
    shortestPathLength(n, graph, dis);
 
    int path1[] = { 1, 2, 3, 4 };
    checkShortestPath(n, path1, dis);
 
    int path2[] = { 1, 3, 4 };
    checkShortestPath(3, path2, dis);
 
    return 0;
}

Java

// Java program for the above approach
class GFG 
{
static int INFINITE = 10000;
 
// Function to store the 
// length of shortest path 
// between all pairs of nodes
static void shortestPathLength(int n, int graph[][],
                                      int dis[][])
{
    // Initializing dis matrix 
    // with current distance value 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dis[i][j] = graph[i][j];
        }
    }
     
    // Floyd-Warshall Algorithm
    for (int k = 0; k < n; k++) 
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                dis[i][j] = Math.min(dis[i][j], 
                                     dis[i][k] + 
                                     dis[k][j]);
            }
        }
    }
}
 
// A function that prints YES if the
// given path is the shortest path
// and prints NO if the given path
// is not shortest
static void checkShortestPath(int length, 
                              int path[], 
                              int dis[][])
{
    // Check if the given path
    // is shortest or not
    // as discussed in above approach
    if (dis[path[0] - 1][path[length - 1] - 1] == length - 1) 
    {
        System.out.println("YES");
    }
    else
    {
        System.out.println("NO");
    }
}
 
// Driver code
public static void main(String[] args)
{
    // Adjacency matrix representing the graph
    int n = 4;
    int graph[][] = { { 0, 1, 1, INFINITE },
                      { INFINITE, 0, 1, INFINITE },
                      { INFINITE, INFINITE, 0, 1 },
                      { 1, INFINITE, INFINITE, 0 } };
                       
    // A matrix to store the length of shortest
    int [][]dis = new int[n][n];
 
    // path between all pairs of vertices
    shortestPathLength(n, graph, dis);
 
    int path1[] = { 1, 2, 3, 4 };
    checkShortestPath(n, path1, dis);
 
    int path2[] = { 1, 3, 4 };
    checkShortestPath(3, path2, dis);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
INFINITE = 10000
 
# Function to store the
# length of shortest path
# between all pairs of nodes
def shortestPathLength(n, graph, dis):
     
    # Initializing dis matrix
    # with current distance value
    for i in range(n):
        for j in range(n):
            dis[i][j] = graph[i][j]
 
    # Floyd-Warshall Algorithm
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis[i][j] = min(dis[i][j], 
                    dis[i][k] + dis[k][j])
 
# A function that prints YES if the
# given path is the shortest path
# and prints NO if the given path
# is not shortest
def checkShortestPath(length, path, dis):
     
    # Check if the given path
    # is shortest or not
    # as discussed in above approach
    if (dis[path[0] - 1][path[length - 1] - 1] == length - 1):
        print("YES")
    else:
        print("NO")
 
# Driver code
 
# Adjacency matrix representing the graph
n = 4
graph = [[ 0, 1, 1, INFINITE],
         [INFINITE, 0, 1, INFINITE],
         [INFINITE, INFINITE, 0, 1],
         [1, INFINITE, INFINITE, 0]]
         
# A matrix to store the length of shortest
dis = [[0 for i in range(n)] 
          for i in range(n)]
 
# path between all pairs of vertices
shortestPathLength(n, graph, dis)
 
path1 = [1, 2, 3, 4]
checkShortestPath(n, path1, dis)
 
path2 = [1, 3, 4]
checkShortestPath(3, path2, dis)
 
# This code is contributed Mohit Kumar

C#

// C# program for the above approach
using System;
 
class GFG 
{
     
static int INFINITE = 10000;
 
// Function to store the 
//.Length of shortest path 
// between all pairs of nodes
static void shortestPathLength(int n, int [,]graph,
                                    int [,]dis)
{
    // Initializing dis matrix 
    // with current distance value 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dis[i, j] = graph[i, j];
        }
    }
     
    // Floyd-Warshall Algorithm
    for (int k = 0; k < n; k++) 
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                dis[i, j] = Math.Min(dis[i, j], 
                                    dis[i, k] + 
                                    dis[k, j]);
            }
        }
    }
}
 
// A function that prints YES if the
// given path is the shortest path
// and prints NO if the given path
// is not shortest
static void checkShortestPath(int length, 
                            int []path, 
                            int [,]dis)
{
    // Check if the given path
    // is shortest or not
    // as discussed in above approach
    if (dis[path[0] - 1, path[length - 1] - 1] == length - 1) 
    {
        Console.WriteLine("YES");
    }
    else
    {
        Console.WriteLine("NO");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    // Adjacency matrix representing the graph
    int n = 4;
    int [,]graph = { { 0, 1, 1, INFINITE },
                    { INFINITE, 0, 1, INFINITE },
                    { INFINITE, INFINITE, 0, 1 },
                    { 1, INFINITE, INFINITE, 0 } };
                         
    // A matrix to store the.Length of shortest
    int [,]dis = new int[n, n];
 
    // path between all pairs of vertices
    shortestPathLength(n, graph, dis);
 
    int []path1 = { 1, 2, 3, 4 };
    checkShortestPath(n, path1, dis);
 
    int []path2 = { 1, 3, 4 };
    checkShortestPath(3, path2, dis);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
let INFINITE = 10000;
 
 
// Function to store the 
// length of shortest path 
// between all pairs of nodes
function shortestPathLength(n,graph,dis)
{
    // Initializing dis matrix 
    // with current distance value 
    for (let i = 0; i < n; i++)
    {
        for (let j = 0; j < n; j++)
        {
            dis[i][j] = graph[i][j];
        }
    }
       
    // Floyd-Warshall Algorithm
    for (let k = 0; k < n; k++) 
    {
        for (let i = 0; i < n; i++)
        {
            for (let j = 0; j < n; j++)
            {
                dis[i][j] = Math.min(dis[i][j], 
                                     dis[i][k] + 
                                     dis[k][j]);
            }
        }
    }
}
 
function checkShortestPath( length,path,dis)
{
    // Check if the given path
    // is shortest or not
    // as discussed in above approach
    if (dis[path[0] - 1][path[length - 1] - 1] == length - 1) 
    {
        document.write("YES<br>");
    }
    else
    {
        document.write("NO<br>");
    }
}
 
let  n = 4;
let graph= [[ 0, 1, 1, INFINITE ],
                      [ INFINITE, 0, 1, INFINITE ],
                      [ INFINITE, INFINITE, 0, 1 ],
                      [ 1, INFINITE, INFINITE, 0 ] ];
                       
let dis = new Array(n);
for(let i=0;i<n;i++)
{
    dis[i]=new Array(n);
    for(let j=0;j<n;j++)
    {
        dis[i][j]=0;
    }
}
// path between all pairs of vertices
shortestPathLength(n, graph, dis);
 
let path1 = [ 1, 2, 3, 4 ];
checkShortestPath(n, path1, dis);
 
let path2 = [ 1, 3, 4 ];
checkShortestPath(3, path2, dis);
 
 
// This code is contributed by patel2127
 
</script>

Output:

NO
YES

Time complexity: O(V^3)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!