Рубрики

Печать путей в алгоритме кратчайшего пути Дейкстры

По заданному графу и исходной вершине в графе найдите кратчайшие пути от источника ко всем вершинам данного графа.

Мы обсудили алгоритм кратчайшего пути Дейкстры в следующих постах.

Реализации, рассмотренные выше, только находят кратчайшие расстояния, но не печатают пути. В этом посте обсуждается печать дорожек.

For example, consider below graph and source as 0,



Output should be
Vertex           Distance         Path
0 -> 1          4        0 1 
0 -> 2          12        0 1 2 
0 -> 3          19        0 1 2 3 
0 -> 4          21        0 7 6 5 4 
0 -> 5          11        0 7 6 5 
0 -> 6          9        0 7 6 
0 -> 7          8        0 7 
0 -> 8          14        0 1 2 8

Идея состоит в том, чтобы создать отдельный массив parent []. Значение parent [v] для вершины v хранит родительскую вершину v в дереве кратчайшего пути. Родитель корня (или исходной вершины) равен -1. Всякий раз, когда мы находим более короткий путь через вершину u, мы делаем u родителем текущей вершины.

Как только мы построили родительский массив, мы можем напечатать путь, используя ниже рекурсивную функцию.

void printPath(int parent[], int j)
{
    // Base Case : If j is source
    if (parent[j]==-1)
        return;

    printPath(parent, parent[j]);

    printf("%d ", j);
}

Ниже приведена полная реализация

C / C ++

// C программа для сингла Дейкстры
// алгоритм поиска кратчайшего пути.
// Программа для матрицы смежности
// представление графа.
#include <stdio.h>
#include <limits.h>

  
// Количество вершин
// в графе
#define V 9

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

int minDistance(int dist[], 

                bool sptSet[])

{

      

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

    int min = INT_MAX, min_index;

  

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

        if (sptSet[v] == false &&

                   dist[v] <= min)

            min = dist[v], min_index = v;

  

    return min_index;

}

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

void printPath(int parent[], int j)

{

      

    // Базовый случай: если j является источником

    if (parent[j] == - 1)

        return;

  

    printPath(parent, parent[j]);

  

    printf("%d ", j);

}

  
// Утилита для печати
// построенное расстояние
// массив

int printSolution(int dist[], int n, 

                      int parent[])

{

    int src = 0;

    printf("Vertex\t Distance\tPath");

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

    {

        printf("\n%d -> %d \t\t %d\t\t%d ",

                      src, i, dist[i], src);

        printPath(parent, i);

    }

}

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

void dijkstra(int graph[V][V], int src)

{

      

    // Выходной массив. расстояние [я]

    // будет держать самое короткое

    // расстояние от источника до меня

    int dist[V]; 

  

    // sptSet [i] будет истинным, если вершина

    // я включен / в кратчайшие

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

    // от src до i завершена

    bool sptSet[V];

  

    // Родительский массив для хранения

    // дерево кратчайшего пути

    int parent[V];

  

    // Инициализируем все расстояния как

    // INFINITE и stpSet [] как false

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

    {

        parent[0] = -1;

        dist[i] = INT_MAX;

        sptSet[i] = false;

    }

  

    // Расстояние исходной вершины

    // от себя всегда 0

    dist[src] = 0;

  

    // Находим кратчайший путь

    // для всех вершин

    for (int count = 0; count < V - 1; count++)

    {

        // Выберите минимальное расстояние

        // вершина из множества

        // вершины еще не обработаны.

        // ты всегда равен src

        // в первой итерации.

        int u = minDistance(dist, sptSet);

  

        // Отметить выбранную вершину

        // как обработано

        sptSet[u] = true;

  

        // Обновляем значение dist для

        // смежные вершины

        // выбранная вершина.

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

  

            // Обновляем dist [v], только если есть

            // нет в sptSet, есть

            // ребро от u до v и

            // общий вес пути от

            // src для v через u меньше

            // чем текущее значение

            // dist [v]

            if (!sptSet[v] && graph[u][v] &&

                dist[u] + graph[u][v] < dist[v])

            {

                parent[v] = u;

                dist[v] = dist[u] + graph[u][v];

            

    }

  

    // выводим построенное

    // массив расстояний

    printSolution(dist, V, parent);

}

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

int main()

{

    // Давайте создадим пример

    // график обсуждался выше

    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},

                       {4, 0, 8, 0, 0, 0, 0, 11, 0},

                        {0, 8, 0, 7, 0, 4, 0, 0, 2},

                        {0, 0, 7, 0, 9, 14, 0, 0, 0},

                        {0, 0, 0, 9, 0, 10, 0, 0, 0},

                        {0, 0, 4, 0, 10, 0, 2, 0, 0},

                        {0, 0, 0, 14, 0, 2, 0, 1, 6},

                        {8, 11, 0, 0, 0, 0, 1, 0, 7},

                        {0, 0, 2, 0, 0, 0, 6, 7, 0}

                    };

  

    dijkstra(graph, 0);

    return 0;

}

Джава

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

  

class DijkstrasAlgorithm {

  

    private static final int NO_PARENT = -1;

  

    // Функция, которая реализует Дейкстру

    // кратчайший путь из одного источника

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

    // используя матрицу смежности

    // представление

    private static void dijkstra(int[][] adjacencyMatrix,

                                        int startVertex)

    {

        int nVertices = adjacencyMatrix[0].length;

  

        // shorttestDistances [i] будет содержать

        // кратчайшее расстояние от источника до меня

        int[] shortestDistances = new int[nVertices];

  

        // добавлено [i] будет true, если вершина i

        // включено / в дерево кратчайшего пути

        // или кратчайшее расстояние от источника до

        // я завершен

        boolean[] added = new boolean[nVertices];

  

        // Инициализируем все расстояния как

        // БЕСКОНЕЧНО и добавлено [] как ложное

        for (int vertexIndex = 0; vertexIndex < nVertices; 

                                            vertexIndex++)

        {

            shortestDistances[vertexIndex] = Integer.MAX_VALUE;

            added[vertexIndex] = false;

        }

          

        // Расстояние от исходной вершины до

        // само по себе всегда 0

        shortestDistances[startVertex] = 0;

  

        // Родительский массив для хранения кратчайшего

        // путь дерева

        int[] parents = new int[nVertices];

  

        // Начальная вершина не

        // есть родитель

        parents[startVertex] = NO_PARENT;

  

        // Находим кратчайший путь для всех

        // вершины

        for (int i = 1; i < nVertices; i++)

        {

  

            // Выбираем минимальную вершину расстояния

            // из множества вершин еще нет

            // обработанный. ближайший вершина

            // всегда равно startNode в

            // первая итерация.

            int nearestVertex = -1;

            int shortestDistance = Integer.MAX_VALUE;

            for (int vertexIndex = 0;

                     vertexIndex < nVertices; 

                     vertexIndex++)

            {

                if (!added[vertexIndex] &&

                    shortestDistances[vertexIndex] < 

                    shortestDistance) 

                {

                    nearestVertex = vertexIndex;

                    shortestDistance = shortestDistances[vertexIndex];

                }

            }

  

            // Пометить выбранную вершину как

            // обработанный

            added[nearestVertex] = true;

  

            // Обновляем значение dist для

            // смежные вершины

            // выбранная вершина.

            for (int vertexIndex = 0;

                     vertexIndex < nVertices; 

                     vertexIndex++) 

            {

                int edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];

                  

                if (edgeDistance > 0

                    && ((shortestDistance + edgeDistance) < 

                        shortestDistances[vertexIndex])) 

                {

                    parents[vertexIndex] = nearestVertex;

                    shortestDistances[vertexIndex] = shortestDistance + 

                                                       edgeDistance;

                }

            }

        }

  

        printSolution(startVertex, shortestDistances, parents);

    }

  

    // Утилита для печати

    // построенные расстояния

    // массив и кратчайшие пути

    private static void printSolution(int startVertex,

                                      int[] distances,

                                      int[] parents)

    {

        int nVertices = distances.length;

        System.out.print("Vertex\t Distance\tPath");

          

        for (int vertexIndex = 0

                 vertexIndex < nVertices; 

                 vertexIndex++) 

        {

            if (vertexIndex != startVertex) 

            {

                System.out.print("\n" + startVertex + " -> ");

                System.out.print(vertexIndex + " \t\t ");

                System.out.print(distances[vertexIndex] + "\t\t");

                printPath(vertexIndex, parents);

            }

        }

    }

  

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

    // из источника в currentVertex

    // используя родительский массив

    private static void printPath(int currentVertex,

                                  int[] parents)

    {

          

        // Базовый случай: исходный узел имеет

        // обработано

        if (currentVertex == NO_PARENT)

        {

            return;

        }

        printPath(parents[currentVertex], parents);

        System.out.print(currentVertex + " ");

    }

  

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

    public static void main(String[] args)

    {

        int[][] adjacencyMatrix = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },

                                    { 4, 0, 8, 0, 0, 0, 0, 11, 0 },

                                    { 0, 8, 0, 7, 0, 4, 0, 0, 2 },

                                    { 0, 0, 7, 0, 9, 14, 0, 0, 0 },

                                    { 0, 0, 0, 9, 0, 10, 0, 0, 0 },

                                    { 0, 0, 4, 0, 10, 0, 2, 0, 0 },

                                    { 0, 0, 0, 14, 0, 2, 0, 1, 6 },

                                    { 8, 11, 0, 0, 0, 0, 1, 0, 7 },

                                    { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

        dijkstra(adjacencyMatrix, 0);

    }

}

  
// Этот код предоставлен Харикришнаном Раджаном

питон

# Python программа для Дейкстры
# один источник самый короткий
# Алгоритм пути. Программа
# для матрицы смежности
# представление графа

  

from collections import defaultdict

  
# Класс для представления графика

class Graph:

  

    # Полезная функция для поиска

    # вершина с минимальным значением dist, из

    # множество вершин еще в очереди

    def minDistance(self,dist,queue):

        # Инициализировать минимальное значение и min_index как -1

        minimum = float("Inf")

        min_index = -1

          

        # из массива dist выберите тот, который

        # имеет минимальное значение и находится в очереди

        for i in range(len(dist)):

            if dist[i] < minimum and i in queue:

                minimum = dist[i]

                min_index = i

        return min_index

  

  

    # Функция для печати кратчайшего пути

    # от источника до j

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

    def printPath(self, parent, j):

          

        # Базовый случай: если j является источником

        if parent[j] == -1

            print j,

            return

        self.printPath(parent , parent[j])

        print j,

          

  

    # Утилита для печати

    # построенное расстояние

    # массив

    def printSolution(self, dist, parent):

        src = 0

        print("Vertex \t\tDistance from Source\tPath")

        for i in range(1, len(dist)):

            print("\n%d --> %d \t\t%d \t\t\t\t\t" % (src, i, dist[i])),

            self.printPath(parent,i)

  

  

    '' 'Функция, которая реализует кратчайший путь Дейкстры с одним источником

    алгоритм для графа, представленного с использованием матрицы смежности

    представление'''

    def dijkstra(self, graph, src):

  

        row = len(graph)

        col = len(graph[0])

  

        # Выходной массив. dist [i] будет держать

        # кратчайшее расстояние от SRC до меня

        # Инициализировать все расстояния как БЕСКОНЕЧНЫЕ

        dist = [float("Inf")] * row

  

        # Родительский массив для хранения

        # кратчайший путь

        parent = [-1] * row

  

        # Расстояние исходной вершины

        # от себя всегда 0

        dist[src] = 0

      

        # Добавить все вершины в очередь

        queue = []

        for i in range(row):

            queue.append(i)

              

        # Найти кратчайший путь для всех вершин

        while queue:

  

            # Выберите минимальную дистальную вершину

            # из множества вершин

            # все еще в очереди

            u = self.minDistance(dist,queue) 

  

            # удалить элемент min

            queue.remove(u)

  

            # Обновить значение dist и parent

            # индекс смежных вершин

            # выбранная вершина. Учитывать только

            # те вершины, которые все еще находятся в

            # очередь

            for i in range(col):

                '' 'Обновите dist [i], только если он находится в очереди, есть

                ребро от вас до я, и общий вес пути от

                Src для I через U меньше, чем текущее значение

                расстояние [я] «»»

                if graph[u][i] and i in queue:

                    if dist[u] + graph[u][i] < dist[i]:

                        dist[i] = dist[u] + graph[u][i]

                        parent[i] = u

  

  

        # распечатать построенный массив расстояний

        self.printSolution(dist,parent)

  

g= Graph()

  

graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],

        [4, 0, 8, 0, 0, 0, 0, 11, 0],

        [0, 8, 0, 7, 0, 4, 0, 0, 2],

        [0, 0, 7, 0, 9, 14, 0, 0, 0],

        [0, 0, 0, 9, 0, 10, 0, 0, 0],

        [0, 0, 4, 14, 10, 0, 2, 0, 0],

        [0, 0, 0, 0, 0, 2, 0, 1, 6],

        [8, 11, 0, 0, 0, 0, 1, 0, 7],

        [0, 0, 2, 0, 0, 0, 6, 7, 0]

        ]

  
# Распечатать решение

g.dijkstra(graph,0)

  

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

C #

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

using System;

  

public class DijkstrasAlgorithm

  

    private static readonly int NO_PARENT = -1; 

  

    // Функция, которая реализует Дейкстру

    // кратчайший путь из одного источника

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

    // используя матрицу смежности

    // представление

    private static void dijkstra(int[,] adjacencyMatrix, 

                                        int startVertex) 

    

        int nVertices = adjacencyMatrix.GetLength(0); 

  

        // shorttestDistances [i] будет содержать

        // кратчайшее расстояние от источника до меня

        int[] shortestDistances = new int[nVertices]; 

  

        // добавлено [i] будет true, если вершина i

        // включено / в дерево кратчайшего пути

        // или кратчайшее расстояние от источника до

        // я завершен

        bool[] added = new bool[nVertices]; 

  

        // Инициализируем все расстояния как

        // БЕСКОНЕЧНО и добавлено [] как ложное

        for (int vertexIndex = 0; vertexIndex < nVertices; 

                                            vertexIndex++) 

        

            shortestDistances[vertexIndex] = int.MaxValue; 

            added[vertexIndex] = false

        

          

        // Расстояние от исходной вершины до

        // само по себе всегда 0

        shortestDistances[startVertex] = 0; 

  

        // Родительский массив для хранения кратчайшего

        // путь дерева

        int[] parents = new int[nVertices]; 

  

        // Начальная вершина не

        // есть родитель

        parents[startVertex] = NO_PARENT; 

  

        // Находим кратчайший путь для всех

        // вершины

        for (int i = 1; i < nVertices; i++) 

        

  

            // Выбираем минимальную вершину расстояния

            // из множества вершин еще нет

            // обработанный. ближайший вершина

            // всегда равно startNode в

            // первая итерация.

            int nearestVertex = -1; 

            int shortestDistance = int.MaxValue; 

            for (int vertexIndex = 0; 

                    vertexIndex < nVertices; 

                    vertexIndex++) 

            

                if (!added[vertexIndex] && 

                    shortestDistances[vertexIndex] < 

                    shortestDistance) 

                

                    nearestVertex = vertexIndex; 

                    shortestDistance = shortestDistances[vertexIndex]; 

                

            

  

            // Пометить выбранную вершину как

            // обработанный

            added[nearestVertex] = true

  

            // Обновляем значение dist для

            // смежные вершины

            // выбранная вершина.

            for (int vertexIndex = 0; 

                    vertexIndex < nVertices; 

                    vertexIndex++) 

            

                int edgeDistance = adjacencyMatrix[nearestVertex,vertexIndex]; 

                  

                if (edgeDistance > 0

                    && ((shortestDistance + edgeDistance) < 

                        shortestDistances[vertexIndex])) 

                

                    parents[vertexIndex] = nearestVertex; 

                    shortestDistances[vertexIndex] = shortestDistance + 

                                                    edgeDistance; 

                

            

        

  

        printSolution(startVertex, shortestDistances, parents); 

    

  

    // Утилита для печати

    // построенные расстояния

    // массив и кратчайшие пути

    private static void printSolution(int startVertex, 

                                    int[] distances, 

                                    int[] parents) 

    

        int nVertices = distances.Length; 

        Console.Write("Vertex\t Distance\tPath"); 

          

        for (int vertexIndex = 0; 

                vertexIndex < nVertices; 

                vertexIndex++) 

        

            if (vertexIndex != startVertex) 

            

                Console.Write("\n" + startVertex + " -> "); 

                Console.Write(vertexIndex + " \t\t "); 

                Console.Write(distances[vertexIndex] + "\t\t"); 

                printPath(vertexIndex, parents); 

            

        

    

  

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

    // из источника в currentVertex

    // используя родительский массив

    private static void printPath(int currentVertex, 

                                int[] parents) 

    

          

        // Базовый случай: исходный узел имеет

        // обработано

        if (currentVertex == NO_PARENT) 

        

            return

        

        printPath(parents[currentVertex], parents); 

        Console.Write(currentVertex + " "); 

    

  

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

    public static void Main(String[] args) 

    

        int[,] adjacencyMatrix = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, 

                                    { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 

                                    { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, 

                                    { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 

                                    { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 

                                    { 0, 0, 4, 0, 10, 0, 2, 0, 0 }, 

                                    { 0, 0, 0, 14, 0, 2, 0, 1, 6 }, 

                                    { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 

                                    { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; 

        dijkstra(adjacencyMatrix, 0); 

    

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

Выход:

Vertex           Distance         Path
0 -> 1          4        0 1 
0 -> 2          12        0 1 2 
0 -> 3          19        0 1 2 3 
0 -> 4          21        0 7 6 5 4 
0 -> 5          11        0 7 6 5 
0 -> 6          9        0 7 6 
0 -> 7          8        0 7 
0 -> 8          14        0 1 2 8 

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

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

Печать путей в алгоритме кратчайшего пути Дейкстры

0.00 (0%) 0 votes