Compruebe si la ruta dada entre dos Nodes de un gráfico representa una ruta más corta

Dado un grafo dirigido no ponderado y consultas Q que consisten en secuencias de recorrido entre dos Nodes del grafo, la tarea es averiguar si las secuencias representan uno de los caminos más cortos entre los dos Nodes.
Ejemplos: 
 

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

Enfoque: 
La idea es utilizar el algoritmo de Floyd Warshall para almacenar la longitud de todos los pares de vértices. Si la longitud del camino más corto entre el Node inicial y final de la secuencia es uno menos que la longitud de la secuencia, entonces la secuencia dada representa uno de los caminos más cortos entre los Nodes. 
A continuación se muestra la implementación del enfoque anterior: 
 

// 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 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 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# 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

<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>

NO
YES

Complejidad del tiempo: O(V^3)