Кратчайший путь из одного источника между двумя городами

Опубликовано: 8 Января, 2022

Дан граф из N узлов и E ребер в виде {U, V, W} такой, что существует ребро между U и V с весом W. Вам дано целое число K и исходный src и целевой dst . Задача - найти путь с наименьшей стоимостью от заданного источника до пункта назначения из K остановок.

Примеры:

Input: N = 3, edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The Cheapest Price is from City 0 to City 2. With just one stop, it just costs 200 which is our Output.

Input: N = 3, edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 0
Output: 500

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Метод 1: использование поиска в глубину

  1. Исследуйте текущий узел и продолжайте изучать его дочерние элементы.
  2. Используйте карту, чтобы сохранить посещенный узел в паре с остановками и расстоянием в качестве значения.
  3. Разбейте дерево рекурсии, если ключ присутствует на карте.
  4. Найдите ответ (минимальную стоимость) для каждого дерева рекурсии и верните его.

Below is the implementation of our approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Structure to implement hashing to
// stores pairs in map
struct pair_hash {
    template <class T1, class T2>
    std::size_t
    operator()(const std::pair<T1, T2>& pair) const
    {
        return std::hash<T1>()(pair.first)
               ^ std::hash<T2>()(pair.second);
    }
};
  
// DFS memoization
vector<vector<int> > adjMatrix;
typedef std::pair<int, int> pair1;
unordered_map<pair1, int, pair_hash> mp;
  
// Function to implement DFS Traversal
long DFSUtility(int node, int stops,
                int dst, int cities)
{
    // Base Case
    if (node == dst)
        return 0;
  
    if (stops < 0) {
        return INT_MAX;
    }
  
    pair<int, int> key(node, stops);
  
    // Find value with key in a map
    if (mp.find(key) != mp.end()) {
        return mp[key];
    }
  
    long ans = INT_MAX;
  
    // Traverse adjacency matrix of
    // source node
    for (int neighbour = 0;
         neighbour < cities;
         ++neighbour) {
  
        long weight
            = adjMatrix[node][neighbour];
  
        if (weight > 0) {
  
            // Recursive DFS call for
            // child node
            long minVal
                = DFSUtility(neighbour,
                             stops - 1,
                             dst, cities);
  
            if (minVal + weight > 0)
                ans = min(ans,
                          minVal
                              + weight);
        }
    }
  
    mp[key] = ans;
  
    // Return ans
    return ans;
}
  
// Function to find the cheapest price
// from given source to destination
int findCheapestPrice(int cities,
                      vector<vector<int> >& flights,
                      int src, int dst, int stops)
{
  
    // Resize Adjacency Marix
    adjMatrix.resize(cities + 1,
                     vector<int>(cities + 1, 0));
  
    // Traverse flight[][]
    for (auto item : flights) {
        // Create Adjacency Matrix
        adjMatrix[item[0]][item[1]] = item[2];
    }
  
    // DFS Call to find shortest path
    long ans = DFSUtility(src, stops,
                          dst, cities);
  
    // Return the cost
    return ans >= INT_MAX ? -1 : (int)ans;
    ;
}
  
// Driver Code
int main()
{
    // Input flight : {Source,
    // Destination, Cost}
    vector<vector<int> > flights
        = { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
  
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
    int sourceCity = 0;
    int destCity = 4;
  
    // Function Call
    long ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity,
        stops);
  
    cout << ans;
    return 0;
}
Output:
6

Сложность времени: O (V + E), где V - количество узлов, а E - ребра.
Вспомогательное пространство: O (V)

Метод 2: использование поиска в ширину

  1. Идея состоит в том, чтобы использовать очередь для выполнения обхода BFS.
  2. Выполните обход от текущего узла и вставьте корневой узел в очередь.
  3. Пройдите по очереди и исследуйте текущий узел и его братьев и сестер. Затем вставьте братьев и сестер узла в очередь.
  4. Изучая каждого брата и сестру, продолжайте вставлять записи в очередь, если стоимость меньше, и обновляйте минимальную стоимость.
  5. Выведите минимальную стоимость после указанного выше обхода.

Below is the implementation of our approach:

C++

// C++ program of the above approach
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <tuple>
#include <unordered_map>
  
using namespace std;
// BSF Memoization
typedef tuple<int, int, int> tupl;
  
// Function to implement BFS
int findCheapestPrice(int cities,
                      vector<vector<int> >& flights,
                      int src, int dst, int stops)
{
    unordered_map<int,
                  vector<pair<int, int> > >
        adjList;
  
    // Traverse flight[][]
    for (auto flight : flights) {
  
        // Create Adjacency Matrix
        adjList[flight[0]].push_back(
            { flight[1], flight[2] });
    }
  
    // < city, distancefromsource > pair
    queue<pair<int, int> >
        q;
    q.push({ src, 0 });
  
    // Store the Result
    int srcDist = INT_MAX;
  
    // Traversing the Matrix
    while (!q.empty() && stops-- >= 0) {
  
        int qSize = q.size();
  
        for (int i = 0; i < qSize; i++) {
            pair<int, int> curr = q.front();
            q.pop();
  
            for (auto next : adjList[curr.first]) {
  
                // If source distance is already
                // least the skip this iteration
                if (srcDist < curr.second
                                  + next.second)
                    continue;
  
                q.push({ next.first,
                         curr.second
                             + next.second });
  
                if (dst == next.first) {
                    srcDist = min(
                        srcDist, curr.second
                                     + next.second);
                }
            }
        }
    }
  
    // Returning the Answer
    return srcDist == INT_MAX ? -1 : srcDist;
}
  
// Driver Code
int main()
{
    // Input flight : {Source,
    // Destination, Cost}
    vector<vector<int> > flights
        = { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
  
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
  
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
  
    // Function Call
    long ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity,
        stops);
    cout << ans;
    return 0;
}
Output:
6

Сложность времени: O (остановок * N * N), где N - произведение городов и размеров в очереди.
Вспомогательное пространство: O (N)

Метод 3: использование алгоритма Дейкстры

  1. Обновите расстояние всех вершин от источника.
  2. Вершины, которые не связаны напрямую с источником, помечаются бесконечностью, а вершины, которые напрямую связаны, обновляются с правильным расстоянием.
  3. Начните с источника и извлеките следующие min вершины. Это обеспечит минимальную стоимость.
  4. Выполняйте релаксацию краев на каждом шаге: D обозначает расстояние, а w обозначает веса
    1. Если D [u] + w (u, z) <D [z], то
    2. D [z] = D [u] + w (u, z)

Here is the implementation of our approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
#include <tuple>
using namespace std;
  
typedef tuple<int, int, int> tupl;
long findCheapestPrice(int cities,
                       vector<vector<int> >& flights,
                       int src, int dst, int stops)
{
    // Adjacency Matrix
    vector<vector<pair<int, int> > > adjList(cities);
  
    // Traverse flight[][]
    for (auto flight : flights) {
        // Create Adjacency Matrix
        adjList[flight[0]].push_back(
            { flight[1], flight[2] });
    }
  
    // Implementing Priority Queue
    priority_queue<tupl, vector<tupl>,
                   greater<tupl> >
        pq;
  
    tupl t = make_tuple(0, src, stops);
    pq.push(t);
  
    // While PQ is not empty
    while (!pq.empty()) {
        tupl t = pq.top();
        pq.pop();
  
        if (src == dst)
            return 0;
  
        int cost = get<0>(t);
        int current = get<1>(t);
        int stop = get<2>(t);
  
        if (current == dst)
  
            // Return the Answer
            return cost;
  
        if (stop >= 0) {
            for (auto next : adjList[current]) {
  
                tupl t = make_tuple((cost
                                     + next.second),
                                    next.first,
                                    stop - 1);
                pq.push(t);
            }
        }
    }
    return -1;
}
  
int main()
{
    // Input flight : {Source,
    // Destination, Cost}
    vector<vector<int> > flights
        = { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
  
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
  
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
  
    // Function Call
    long ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity, stops);
    cout << ans;
    return 0;
}
Output:
6

Сложность времени: O (E + V log V), где V - количество узлов, а E - ребра.
Вспомогательное пространство: O (V)

Метод 4: Использование Bellmon Ford

  1. Инициализируйте расстояния от источника до всех вершин как бесконечные, а расстояние до самого источника как 0.
  2. Выполняйте релаксацию краев на каждом шаге: D обозначает расстояние, а w обозначает веса
    • Если D [u] + w (u, z) <D [z], то D [z] = D [u] + w (u, z)
  3. Алгоритм был модифицирован для решения данной задачи, вместо того, чтобы расслаблять граф V-1 раз, мы будем делать это для заданного количества остановок.

Below is the implementation of the above approach

C++

// C++ program of the above Approach
#include <bits/stdc++.h>
#include <vector>
using namespace std;
  
// Function to find the cheapest cost
// from source to destination using K stops
int findCheapestPrice(int cities,
                      vector<vector<int> >& flights,
                      int src, int dst, int stops)
{
    // Dstance from source to all other nodes
    vector<int> dist(cities, INT_MAX);
    dist[src] = 0;
  
    // Do relaxation for V-1 vertices
    // here we need for K stops so we
    // will do relaxation for k+1 stops
    for (int i = 0; i <= stops; i++) {
  
        vector<int> intermediate(dist);
  
        for (auto flight : flights) {
  
            if (dist[flight[0]] != INT_MAX) {
                intermediate[flight[1]]
                    = min(intermediate[flight[1]],
                          dist[flight[0]]
                              + flight[2]);
            }
        }
  
        // Update the distance vector
        dist = intermediate;
    }
  
    // Return the final cost
    return dist[dst] == INT_MAX ? -1 : dist[dst];
}
  
// Driver Code
int main()
{
    // Input flight : {Source, Destination, Cost}
    vector<vector<int> > flights
Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023