Рубрики

Кратчайший путь в взвешенном графике, где вес ребра равен 1 или 2

Для заданного графа, где вес каждого ребра равен 1 или 2, найдите кратчайший путь от заданной исходной вершины 's' до заданной конечной вершины 't'. Ожидаемая сложность времени O (V + E).
Простым решением является использование алгоритма кратчайшего пути Дейкстры , мы можем получить кратчайший путь за O (E + VLogV) времени.

Как это сделать за время O (V + E)? Идея состоит в том, чтобы использовать BFS . Одним из важных замечаний о BFS является то, что путь, используемый в BFS, всегда имеет наименьшее количество ребер между любыми двумя вершинами. Поэтому, если все ребра имеют одинаковый вес, мы можем использовать BFS, чтобы найти кратчайший путь. Для этой задачи мы можем изменить график и разбить все ребра веса 2 на два ребра веса 1 каждый. В модифицированном графе мы можем использовать BFS, чтобы найти кратчайший путь.

Сколько нужно новых промежуточных вершин? Нам нужно добавить новую промежуточную вершину для каждой исходной вершины. Причина проста: если мы добавим промежуточную вершину x между u и v и если мы добавим одну и ту же вершину между y и z, то новые пути u к z и y к v будут добавлены в граф, который, возможно, был отмечен в исходном графе. , Поэтому в графе с V вершинами нам понадобится V дополнительных вершин.

Ниже приведена реализация вышеуказанной идеи на C ++. В приведенной ниже реализации 2 * V вершины создаются в графе, и для каждого ребра (u, v) мы разбиваем его на два ребра (u, u + V) и (u + V, w). Таким образом, мы гарантируем, что разные промежуточные вершины добавляются для каждой исходной вершины.

C / C ++

// Программируем кратчайший путь от заданной исходной вершины 's' до
// заданная конечная вершина 't'. Ожидаемая сложность времени
// является O (V + E).
#include<bits/stdc++.h>

using namespace std;

  
// Этот класс представляет ориентированный граф с использованием смежности
// представление списка

class Graph

{

    int V;    // Количество вершин

    list<int> *adj;    // списки смежности

public:

    Graph(int V);  // Конструктор

    void addEdge(int v, int w, int weight); // добавляет ребро

  

    // находит кратчайший путь от исходной вершины 's' до

    // целевая вершина 'd'.

    int findShortestPath(int s, int d);

  

    // выводим кратчайший путь из исходной вершины 's' в

    // целевая вершина 'd'.

    int printShortestPath(int parent[], int s, int d);

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[2*V];

}

  

void Graph::addEdge(int v, int w, int weight)

{

    // разбить все ребра веса 2 на два

    // ребра весом 1 каждый. Промежуточный

    // номер вершины максимальный номер вершины + 1,

    // это В.

    if (weight==2)

    {

        adj[v].push_back(v+V);

        adj[v+V].push_back(w);

    }

    else // Вес 1

        adj[v].push_back(w); // Добавить w в список v.

}

  
// Для печати кратчайшего пути, хранящегося в parent []

int Graph::printShortestPath(int parent[], int s, int d)

{

    static int level = 0;

  

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

    if (parent[s] == -1)

    {

        cout << "Shortest Path between " << s << " and "

             << d << " is "  << s << " ";

        return level;

    }

  

    printShortestPath(parent, parent[s], d);

  

    level++;

    if (s < V)

        cout << s << " ";

  

    return level;

}

  
// Эта функция в основном выполняет BFS и печатает
// кратчайший путь от src до dest. Предполагается
// вес каждого ребра равен 1

int Graph::findShortestPath(int src, int dest)

{

    // Пометить все вершины как не посещенные

    bool *visited = new bool[2*V];

    int *parent = new int[2*V];

  

    // Инициализируем parent [] и visit []

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

    {

        visited[i] = false;

        parent[i] = -1;

    }

  

    // Создать очередь для BFS

    list<int> queue;

  

    // Помечаем текущий узел как посещенный и ставим его в очередь

    visited[src] = true;

    queue.push_back(src);

  

    // 'i' будет использоваться для получения всех смежных вершин вершины

    list<int>::iterator i;

  

    while (!queue.empty())

    {

        // Удаление вершины из очереди и печать ее

        int s = queue.front();

  

        if (s == dest)

            return printShortestPath(parent, s, dest);

  

        queue.pop_front();

  

        // Получаем все смежные вершины удаленной вершины s

        // Если соседний объект не был посещен, отметьте его

        // посетили и поставили в очередь

        for (i = adj[s].begin(); i != adj[s].end(); ++i)

        {

            if (!visited[*i])

            {

                visited[*i] = true;

                queue.push_back(*i);

                parent[*i] = s;

            }

        }

    }

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

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

    int V = 4;

    Graph g(V);

    g.addEdge(0, 1, 2);

    g.addEdge(0, 2, 2);

    g.addEdge(1, 2, 1);

    g.addEdge(1, 3, 1);

    g.addEdge(2, 0, 1);

    g.addEdge(2, 3, 2);

    g.addEdge(3, 3, 2);

  

    int src = 0, dest = 3;

    cout << "\nShortest Distance between " << src

         << " and " << dest << " is "

         << g.findShortestPath(src, dest);

  

    return 0;

}

питон

'' 'Запрограммировать кратчайший путь от заданной исходной вершины s к

    заданная вершина назначения t. Ожидаемая сложность времени

    это O (V + E) '' '

from collections import defaultdict

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

class Graph:

   

    def __init__(self,vertices):

        self.V = vertices #No. вершин

        self.V_org = vertices

        self.graph = defaultdict(list) # словарь по умолчанию для хранения графика

   

    # функция для добавления ребра на график

    def addEdge(self,u,v,w):

        if w == 1:

            self.graph[u].append(v)

        else:   

            '' 'разделить все ребра веса 2 на два

            ребра весом 1 каждый. Промежуточный

            номер вершины - максимальное число вершин + 1,

            это В. '' '

            self.graph[u].append(self.V)

            self.graph[self.V].append(v)

            self.V = self.V + 1

      

    # Для печати кратчайшего пути, хранящегося в parent []

    def printPath(self, parent, j):

        Path_len = 1

        if parent[j] == -1 and j < self.V_org : # Базовый случай: если j является источником

            print j,

            return 0 # когда родитель [-1], то длина пути = 0

        l = self.printPath(parent , parent[j])

  

        # длина пути

        Path_len = l + Path_len

  

        # печатать узел, только если его длина меньше исходной.

        # т.е. не печатать ни один новый узел, который был добавлен позже

        if j < self.V_org : 

            print j,

  

        return Path_len

  

    '' 'Эта функция в основном выполняет BFS и печатает

        кратчайший путь от SRC до Dest. Предполагается

        вес каждого ребра равен 1 '' '

    def findShortestPath(self,src, dest):

  

        # Отметить все вершины как не посещенные

        # Инициализировать родительский [] и посещенный []

        visited =[False]*(self.V)

        parent =[-1]*(self.V)

   

        # Создать очередь для BFS

        queue=[]

   

        # Отметить исходный узел как посещенный и поставить его в очередь

        queue.append(src)

        visited[src] = True

   

        while queue :

              

            # Удаление вершины из очереди

            s = queue.pop(0)

              

            # если s = dest, выведите путь и вернитесь

            if s == dest:

                return self.printPath(parent, s)

                  

   

            # Получить все смежные вершины в удаленной вершине s

            # Если соседний объект не посещался, отметьте его

            # посетил и поставил в очередь

            for i in self.graph[s]:

                if visited[i] == False:

                    queue.append(i)

                    visited[i] = True

                    parent[i] = s

   

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

g = Graph(4)

g.addEdge(0, 1, 2)

g.addEdge(0, 2, 2)

g.addEdge(1, 2, 1)

g.addEdge(1, 3, 1)

g.addEdge(2, 0, 1)

g.addEdge(2, 3, 2)

g.addEdge(3, 3, 2)

  

src = 0; dest = 3

print ("Shortest Path between %d and %d is  " %(src, dest)),

l = g.findShortestPath(src, dest)

print ("\nShortest Distance between %d and %d is %d " %(src, dest, l)),

  
# Этот код предоставлен Ниламом Ядавом


Выход :

Shortest Path between 0 and 3 is 0 1 3 
Shortest Distance between 0 and 3 is 3

Как этот подход O (V + E)? В худшем случае все ребра имеют вес 2, и нам нужно выполнить O (E) операции, чтобы разбить все ребра и 2V вершины, поэтому сложность по времени становится O (E) + O (V + E), которая равна O (V +). E).

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

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

Кратчайший путь в взвешенном графике, где вес ребра равен 1 или 2

0.00 (0%) 0 votes