Рубрики

Проверьте, представляет ли данный путь между двумя узлами графа кратчайшие пути

Графы

Для заданного невзвешенного ориентированного графа и Q запросов, состоящих из последовательностей обхода между двумя узлами графа, задача состоит в том, чтобы выяснить, представляют ли последовательности один из кратчайших путей между двумя узлами.

Примеры:

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

Подходить:
Идея состоит в том, чтобы использовать алгоритм Флойда Варшалла для хранения длины всех пар вершин. Если длина кратчайшего пути между начальным и конечным узлом последовательности на единицу меньше длины последовательности, то данная последовательность представляет один из самых коротких путей между узлами.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для
// вышеуказанный подход
#include <bits/stdc++.h>

using namespace std;

#define INFINITE 10000

  
// Функция для хранения
// длина кратчайшего пути
// между всеми парами узлов

void shortestPathLength(int n, int graph[4][4], int dis[4][4])

{

  // Инициализация дис-матрицы

  // с текущим значением расстояния

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

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

          dis[i][j] = graph[i][j];

      }

  }

  

  // Алгоритм Флойда-Варшалла

  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]);

      }

    }

  }

}

  
// Функция, которая печатает YES, если
// данный путь является кратчайшим путем
// и печатает НЕТ, если данный путь
// не самый короткий

void checkShortestPath(int length, int path[], int dis[4][4])

{

  // Проверяем, указан ли путь

  // самый короткий или нет

  // как обсуждено в вышеупомянутом подходе

  if (dis[path[0] - 1][path[length - 1] - 1] == length - 1) {

      cout << "YES" << endl;

  }

  else {

      cout << "NO" << endl;

  }

}

  
// Код драйвера

int main()

{

    // Матрица смежности, представляющая граф

    const int n = 4;

    int graph[n][n] = { { 0, 1, 1, INFINITE },

                        { INFINITE, 0, 1, INFINITE },

                        { INFINITE, INFINITE, 0, 1 },

                        { 1, INFINITE, INFINITE, 0 } };

    // Матрица для хранения длины кратчайшего

    int dis[n][n];

  

    // путь между всеми парами вершин

    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-программа для вышеуказанного подхода

class GFG 

{

static int INFINITE = 10000;

  
// Функция для хранения
// длина кратчайшего пути
// между всеми парами узлов

static void shortestPathLength(int n, int graph[][],

                                      int dis[][])

{

    // Инициализация дис-матрицы

    // с текущим значением расстояния

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

    {

        for (int j = 0; j < n; j++)

        {

            dis[i][j] = graph[i][j];

        }

    }

      

    // Алгоритм Флойда-Варшалла

    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]);

            }

        }

    }

}

  
// Функция, которая печатает YES, если
// данный путь является кратчайшим путем
// и печатает НЕТ, если данный путь
// не самый короткий

static void checkShortestPath(int length, 

                              int path[], 

                              int dis[][])

{

    // Проверяем, указан ли путь

    // самый короткий или нет

    // как обсуждено в вышеупомянутом подходе

    if (dis[path[0] - 1][path[length - 1] - 1] == length - 1) 

    {

        System.out.println("YES");

    }

    else 

    {

        System.out.println("NO");

    }

}

  
// Код драйвера

public static void main(String[] args)

{

    // Матрица смежности, представляющая граф

    int n = 4;

    int graph[][] = { { 0, 1, 1, INFINITE },

                      { INFINITE, 0, 1, INFINITE },

                      { INFINITE, INFINITE, 0, 1 },

                      { 1, INFINITE, INFINITE, 0 } };

                        

    // Матрица для хранения длины кратчайшего

    int [][]dis = new int[n][n];

  

    // путь между всеми парами вершин

    shortestPathLength(n, graph, dis);

  

    int path1[] = { 1, 2, 3, 4 };

    checkShortestPath(n, path1, dis);

  

    int path2[] = { 1, 3, 4 };

    checkShortestPath(3, path2, dis);

}
}

  
// Этот код предоставлен Rajput-Ji

python3

# Python3 программа для вышеуказанного подхода

INFINITE = 10000

  
# Функция для хранения
# длина кратчайшего пути
# между всеми парами узлов

def shortestPathLength(n, graph, dis):

      

    # Инициализация дис-матрицы

    # с текущим значением расстояния

    for i in range(n):

        for j in range(n):

            dis[i][j] = graph[i][j]

  

    Алгоритм Флойда-Варшалла

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

  
# Функция, которая печатает YES, если
# данный путь является кратчайшим путем
# и печатает НЕТ, если данный путь
# не самый короткий

def checkShortestPath(length, path, dis):

      

    # Проверьте, указан ли путь

    # самое короткое или нет

    # как обсуждено в вышеупомянутом подходе

    if (dis[path[0] - 1][path[length - 1] - 1] == length - 1):

        print("YES")

    else:

        print("NO")

  
# Код драйвера

  
# Матрица смежности, представляющая график

n = 4

graph = [[ 0, 1, 1, INFINITE],

         [INFINITE, 0, 1, INFINITE],

         [INFINITE, INFINITE, 0, 1],

         [1, INFINITE, INFINITE, 0]]

          
# Матрица для хранения длины кратчайшего

dis = [[0 for i in range(n)] 

          for i in range(n)]

  
# путь между всеми парами вершин
shortestPathLength(n, graph, dis)

  

path1 = [1, 2, 3, 4]

checkShortestPath(n, path1, dis)

  

path2 = [1, 3, 4]

checkShortestPath(3, path2, dis)

  
# Этот код предоставлен Мохит Кумар

C #

// C # программа для вышеуказанного подхода

using System;

  

class GFG 

{

      

static int INFINITE = 10000;

  
// Функция для хранения
//.Длина кратчайшего пути
// между всеми парами узлов

static void shortestPathLength(int n, int [,]graph,

                                    int [,]dis)

{

    // Инициализация дис-матрицы

    // с текущим значением расстояния

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

    {

        for (int j = 0; j < n; j++)

        {

            dis[i, j] = graph[i, j];

        }

    }

      

    // Алгоритм Флойда-Варшалла

    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]);

            }

        }

    }

}

  
// Функция, которая печатает YES, если
// данный путь является кратчайшим путем
// и печатает НЕТ, если данный путь
// не самый короткий

static void checkShortestPath(int length, 

                            int []path, 

                            int [,]dis)

{

    // Проверяем, указан ли путь

    // самый короткий или нет

    // как обсуждено в вышеупомянутом подходе

    if (dis[path[0] - 1, path[length - 1] - 1] == length - 1) 

    {

        Console.WriteLine("YES");

    }

    else

    {

        Console.WriteLine("NO");

    }

}

  
// Код драйвера

public static void Main(String[] args)

{

    // Матрица смежности, представляющая граф

    int n = 4;

    int [,]graph = { { 0, 1, 1, INFINITE },

                    { INFINITE, 0, 1, INFINITE },

                    { INFINITE, INFINITE, 0, 1 },

                    { 1, INFINITE, INFINITE, 0 } };

                          

    // Матрица для хранения. Длина кратчайшего

    int [,]dis = new int[n, n];

  

    // путь между всеми парами вершин

    shortestPathLength(n, graph, dis);

  

    int []path1 = { 1, 2, 3, 4 };

    checkShortestPath(n, path1, dis);

  

    int []path2 = { 1, 3, 4 };

    checkShortestPath(3, path2, dis);

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

NO
YES

Сложность времени: O (V ^ 3)

Рекомендуемые посты:

Проверьте, представляет ли данный путь между двумя узлами графа кратчайшие пути

0.00 (0%) 0 votes