Рубрики

Кратчайший путь с ровно k ребрами в ориентированном и взвешенном графе

Учитывая направленную и две вершины 'u' и 'v' в нем, найдите кратчайший путь от 'u' до 'v' с ровно k ребрами на пути.

Граф представлен как матричное представление смежности, где значение графа [i] [j] указывает вес ребра от вершины i до вершины j, а значение INF (бесконечное) указывает на отсутствие ребра от i до j.

Например, рассмотрим следующий график. Пусть источник 'u' будет вершиной 0, пункт назначения 'v' будет 3, а k будет 2. Есть два обхода длины 2, обходы: {0, 2, 3} и {0, 1, 3}. Самый короткий из них — {0, 2, 3}, а вес пути — 3 + 6 = 9.

Идея состоит в том, чтобы просмотреть все пути длины k от u до v, используя подход, описанный в предыдущем посте, и вернуть вес кратчайшего пути. Простое решение состоит в том, чтобы начать с u, перейти ко всем смежным вершинам и повторить для смежных вершин с k как k-1, источником как смежная вершина и пунктом назначения как v. Ниже приведены реализации этого простого решения на C ++ и Java.

C ++

// C ++ программа для поиска кратчайшего пути с ровно k ребрами
#include <iostream>
#include <climits>

using namespace std;

  
// Определяем количество вершин в графе и начальное значение
#define V 4
#define INF INT_MAX

  
// Наивная рекурсивная функция для подсчета шагов от u до v с k ребрами

int shortestPath(int graph[][V], int u, int v, int k)

{

   // Базовые случаи

   if (k == 0 && u == v)             return 0;

   if (k == 1 && graph[u][v] != INF) return graph[u][v];

   if (k <= 0)                       return INF;

  

   // Инициализировать результат

   int res = INF;

  

   // Перейти ко всем смежным объектам и повторить

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

   {

       if (graph[u][i] != INF && u != i && v != i)

       {

           int rec_res = shortestPath(graph, i, v, k-1);

           if (rec_res != INF)

              res = min(res, graph[u][i] + rec_res);

       }

   }

   return res;

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    / * Давайте создадим график, показанный на диаграмме выше * /

     int graph[V][V] = { {0, 10, 3, 2},

                        {INF, 0, INF, 7},

                        {INF, INF, 0, 6},

                        {INF, INF, INF, 0}

                      };

    int u = 0, v = 3, k = 2;

    cout << "Weight of the shortest path is " <<

          shortestPath(graph, u, v, k);

    return 0;

}

Джава

// Java-программа на основе динамического программирования для поиска кратчайшего пути
// с ровно k ребрами

import java.util.*;

import java.lang.*;

import java.io.*;

  

class ShortestPath

{

    // Определяем количество вершин в графе и начальное значение

    static final int V = 4;

    static final int INF = Integer.MAX_VALUE;

  

    // Наивная рекурсивная функция для подсчета шагов от u до v

    // с k ребрами

    int shortestPath(int graph[][], int u, int v, int k)

    {

        // Базовые случаи

        if (k == 0 && u == v)             return 0;

        if (k == 1 && graph[u][v] != INF) return graph[u][v];

        if (k <= 0)                       return INF;

  

        // Инициализировать результат

        int res = INF;

  

        // Перейти ко всем смежным объектам и повторить

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

        {

            if (graph[u][i] != INF && u != i && v != i)

            {

                int rec_res = shortestPath(graph, i, v, k-1);

                if (rec_res != INF)

                    res = Math.min(res, graph[u][i] + rec_res);

            }

        }

        return res;

    }

  

    public static void main (String[] args)

    {

        / * Давайте создадим график, показанный на диаграмме выше * /

        int graph[][] = new int[][]{ {0, 10, 3, 2},

                                     {INF, 0, INF, 7},

                                     {INF, INF, 0, 6},

                                     {INF, INF, INF, 0}

                                   };

        ShortestPath t = new ShortestPath();

        int u = 0, v = 3, k = 2;

        System.out.println("Weight of the shortest path is "+

                           t.shortestPath(graph, u, v, k));

    }

}

python3

# Python3 программа для поиска кратчайшего пути
# с ровно k ребрами

  
# Определить количество вершин в графе
# и бесконечное значение

  
# Наивная рекурсивная функция для подсчета
# идет от u к v с k ребрами

def shortestPath(graph, u, v, k):

    V = 4

    INF = 999999999999

      

    # Базовые случаи

    if k == 0 and u == v:

        return 0

    if k == 1 and graph[u][v] != INF:

        return graph[u][v] 

    if k <= 0:

        return INF 

  
# Инициализировать результат

    res = INF 

  
# Перейти ко всем окрестностям и повторить

    for i in range(V):

        if graph[u][i] != INF and u != i and v != i:

            rec_res = shortestPath(graph, i, v, k - 1

            if rec_res != INF:

                res = min(res, graph[u][i] + rec_res)

    return res

  
Код водителя

if __name__ == '__main__':

    INF = 999999999999

      

    # Давайте создадим показанный график

    # на диаграмме выше

    graph = [[0, 10, 3, 2],

             [INF, 0, INF, 7],

             [INF, INF, 0, 6],

             [INF, INF, INF, 0]]

    u = 0

    v = 3

    k = 2

    print("Weight of the shortest path is",

              shortestPath(graph, u, v, k))

  
# Этот код предоставлен PranchalK

C #

// Программа на C # для динамического программирования
// найти кратчайший путь с ровно k ребрами

using System;

  

class GFG

{

      
// Определяем количество вершин в
// график и начальное значение

const int V = 4;

const int INF = Int32.MaxValue;

  
// Наивная рекурсивная функция для подсчета
// идет от u к v с k ребрами

int shortestPath(int[,] graph, int u, 

                 int v, int k)

{

    // Базовые случаи

    if (k == 0 && u == v)         return 0;

    if (k == 1 && graph[u, v] != INF) return graph[u, v];

    if (k <= 0)                 return INF;

  

    // Инициализировать результат

    int res = INF;

  

    // Перейти ко всем смежным объектам и повторить

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

    {

        if (graph[u, i] != INF && u != i && v != i)

        {

            int rec_res = shortestPath(graph, i, v, k - 1);

            if (rec_res != INF)

                res = Math.Min(res, graph[u, i] + rec_res);

        }

    }

    return res;

}

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

public static void Main ()

{

    / * Давайте создадим график

       показано на диаграмме выше * /

    int[,] graph = new int[,]{{0, 10, 3, 2},

                              {INF, 0, INF, 7},

                              {INF, INF, 0, 6},

                              {INF, INF, INF, 0}};

    GFG t = new GFG();

    int u = 0, v = 3, k = 2;

    Console.WriteLine("Weight of the shortest path is "+

                      t.shortestPath(graph, u, v, k));

}
}

  
// Этот код предоставлен Akanksha Rai


Выход:

Weight of the shortest path is 9

Наихудшая временная сложность вышеуказанной функции — O (V k ), где V — количество вершин в данном графе. Мы можем просто проанализировать сложность времени, нарисовав дерево рекурсии. Худшее происходит для полного графика. В худшем случае каждый внутренний узел дерева рекурсии будет иметь ровно V дочерних элементов.
Мы можем оптимизировать вышеуказанное решение с помощью динамического программирования . Идея состоит в том, чтобы создать трехмерную таблицу, в которой первое измерение является источником, второе измерение является назначением, третье измерение — это количество ребер от источника до назначения, а значение — это число прогулок. Как и другие проблемы с динамическим программированием , мы заполняем трехмерную таблицу снизу вверх.

C ++

// Программа C ++ на основе динамического программирования для поиска кратчайшего пути с
// ровно k ребер
#include <iostream>
#include <climits>

using namespace std;

  
// Определяем количество вершин в графе и начальное значение
#define V 4
#define INF INT_MAX

  
// Функция на основе динамического программирования, чтобы найти кратчайший путь из
// u к v с ровно k ребрами.

int shortestPath(int graph[][V], int u, int v, int k)

{

    // Таблица заполняется с помощью DP. Значение sp [i] [j] [e] будет хранить

    // вес кратчайшего пути от i до j с ровно k ребрами

    int sp[V][V][k+1];

  

    // Цикл для количества ребер от 0 до k

    for (int e = 0; e <= k; e++)

    {

        for (int i = 0; i < V; i++)  // для источника

        {

            for (int j = 0; j < V; j++) // для пункта назначения

            {

                // инициализируем значение

                sp[i][j][e] = INF;

  

                // из базовых случаев

                if (e == 0 && i == j)

                    sp[i][j][e] = 0;

                if (e == 1 && graph[i][j] != INF)

                    sp[i][j][e] = graph[i][j];

  

                // перейти к соседнему, только когда число ребер больше 1

                if (e > 1)

                {

                    for (int a = 0; a < V; a++)

                    {

                        // Должно быть ребро от i до a и a

                        // не должно совпадать с i или j

                        if (graph[i][a] != INF && i != a &&

                            j!= a && sp[a][j][e-1] != INF)

                          sp[i][j][e] = min(sp[i][j][e], graph[i][a] +

                                                       sp[a][j][e-1]);

                    }

                }

           }

        }

    }

    return sp[u][v][k];

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    / * Давайте создадим график, показанный на диаграмме выше * /

     int graph[V][V] = { {0, 10, 3, 2},

                        {INF, 0, INF, 7},

                        {INF, INF, 0, 6},

                        {INF, INF, INF, 0}

                      };

    int u = 0, v = 3, k = 2;

    cout << shortestPath(graph, u, v, k);

    return 0;

}

Джава

// Java-программа на основе динамического программирования, чтобы найти кратчайший путь с
// ровно k ребер

import java.util.*;

import java.lang.*;

import java.io.*;

  

class ShortestPath

{

    // Определяем количество вершин в графе и начальное значение

    static final int V = 4;

    static final int INF = Integer.MAX_VALUE;

  

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

    // от u до v с ровно k ребрами.

    int shortestPath(int graph[][], int u, int v, int k)

    {

        // Таблица заполняется с помощью DP. Значение sp [i] [j] [e] будет

        // сохраняем вес кратчайшего пути от i до j точно

        // k ребер

        int sp[][][] = new int[V][V][k+1];

  

        // Цикл для количества ребер от 0 до k

        for (int e = 0; e <= k; e++)

        {

            for (int i = 0; i < V; i++)  // для источника

            {

                for (int j = 0; j < V; j++) // для пункта назначения

                {

                    // инициализируем значение

                    sp[i][j][e] = INF;

  

                    // из базовых случаев

                    if (e == 0 && i == j)

                        sp[i][j][e] = 0;

                    if (e == 1 && graph[i][j] != INF)

                        sp[i][j][e] = graph[i][j];

  

                    // перейти к соседнему, только когда число ребер

                    // более 1

                    if (e > 1)

                    {

                        for (int a = 0; a < V; a++)

                        {

                            // Должно быть ребро от i до a и

                            // a не должен совпадать с i или j

                            if (graph[i][a] != INF && i != a &&

                                    j!= a && sp[a][j][e-1] != INF)

                                sp[i][j][e] = Math.min(sp[i][j][e],

                                          graph[i][a] + sp[a][j][e-1]);

                        }

                    }

                }

            }

        }

        return sp[u][v][k];

    }

  

    public static void main (String[] args)

    {

        / * Давайте создадим график, показанный на диаграмме выше * /

        int graph[][] = new int[][]{ {0, 10, 3, 2},

                                     {INF, 0, INF, 7},

                                     {INF, INF, 0, 6},

                                     {INF, INF, INF, 0}

                                   };

        ShortestPath t = new ShortestPath();

        int u = 0, v = 3, k = 2;

        System.out.println("Weight of the shortest path is "+

                           t.shortestPath(graph, u, v, k));

    }

}
// Этот код предоставлен Aakash Hasija

python3

# Динамическое программирование на основе Python3
# программа для поиска кратчайшего пути с

  
# Функция динамического программирования
# найти кратчайший путь от вас до v
# ровно с k ребрами.

def shortestPath(graph, u, v, k):

    global V, INF

      

    # Таблица заполняется с помощью DP.

    # значение sp [i] [j] [e] будет хранить вес

    # кратчайшего пути от i до j

    # с ровно k ребрами

    sp = [[None] * V for i in range(V)]

    for i in range(V):

        for j in range(V):

            sp[i][j] = [None] * (k + 1)

  

    # Цикл для количества ребер от 0 до k

    for e in range(k + 1):

        for i in range(V): # для источника

            for j in range(V): # для пункта назначения

              

                # инициализировать значение

                sp[i][j][e] = INF

  

                # из базовых случаев

                if (e == 0 and i == j): 

                    sp[i][j][e] = 0

                if (e == 1 and graph[i][j] != INF):

                    sp[i][j][e] = graph[i][j] 

  

                # переходить к соседним только когда номер

                Количество ребер больше 1

                if (e > 1):

                    for a in range(V):

                          

                        # Там должно быть преимущество от

                        # я к а не должно быть

                        # так же, как я или j

                        if (graph[i][a] != INF and i != a and 

                             j!= a and sp[a][j][e - 1] != INF): 

                            sp[i][j][e] = min(sp[i][j][e], graph[i][a] + 

                                              sp[a][j][e - 1])

                          

    return sp[u][v][k]

  
Код водителя

  
# Определить количество вершин в
# график и начальное значение

V = 4

INF = 999999999999

  
# Давайте создадим показанный график
# на диаграмме выше

graph = [[0, 10, 3, 2], 

         [INF, 0, INF, 7], 

         [INF, INF, 0, 6], 

         [INF, INF, INF, 0]]

u = 0

v = 3

k = 2

print("Weight of the shortest path is",

          shortestPath(graph, u, v, k))

  
# Этот код предоставлен PranchalK

C #

// Программа на C # для динамического программирования, чтобы найти
// кратчайший путь с ровно k ребрами

using System;

  

class GFG 

      
// Определяем количество вершин в графе
// и бесконечное значение

static readonly int V = 4; 

static readonly int INF = int.MaxValue; 

  
// Функция на основе динамического программирования для
// найти кратчайший путь от u до v
// с ровно k ребрами.

int shortestPath(int [,]graph, int u, int v, int k) 

    // Таблица заполняется с помощью DP. Значение

    // sp [i] [j] [e] будет хранить вес самого короткого

    // путь от i до j с ровно k ребрами

    int [,,]sp = new int[V, V, k + 1]; 

  

    // Цикл для количества ребер от 0 до k

    for (int e = 0; e <= k; e++) 

    

        for (int i = 0; i < V; i++) // для источника

        

            for (int j = 0; j < V; j++) // для пункта назначения

            

                // инициализируем значение

                sp[i, j, e] = INF; 

  

                // из базовых случаев

                if (e == 0 && i == j) 

                    sp[i, j, e] = 0; 

                if (e == 1 && graph[i, j] != INF) 

                    sp[i, j, e] = graph[i, j]; 

  

                // перейти к соседнему, только когда номер

                // ребер больше 1

                if (e > 1) 

                

                    for (int a = 0; a < V; a++) 

                    

                        // Должно быть ребро от i до a и

                        // a не должен совпадать с i или j

                        if (graph[i, a] != INF && i != a && 

                                j!= a && sp[a, j, e - 1] != INF) 

                            sp[i, j, e] = Math.Min(sp[i, j, e], 

                                          graph[i, a] + sp[a, j, e - 1]); 

                    

                

            

        

    

    return sp[u, v, k]; 

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

public static void Main(String[] args) 

    / * Давайте создадим график, показанный на диаграмме выше * /

    int [,]graph = new int[,]{ {0, 10, 3, 2}, 

                               {INF, 0, INF, 7}, 

                               {INF, INF, 0, 6}, 

                               {INF, INF, INF, 0} }; 

    GFG t = new GFG(); 

    int u = 0, v = 3, k = 2; 

    Console.WriteLine("Weight of the shortest path is "

                        t.shortestPath(graph, u, v, k)); 


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


Выход:

Weight of the shortest path is 9

Временная сложность вышеупомянутого решения на основе DP составляет O (V 3 K), что намного лучше, чем простое решение.

Эта статья предоставлена Abhishek . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Кратчайший путь с ровно k ребрами в ориентированном и взвешенном графе

0.00 (0%) 0 votes