Рубрики

Программа Python для алгоритма кратчайшего пути Дейкстры | Жадный Алго-7

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

Алгоритм Дейкстры очень похож на алгоритм Прима для минимального остовного дерева . Как и MST Prim, мы генерируем SPT (дерево кратчайшего пути) с заданным источником в качестве root. Мы поддерживаем два набора, один набор содержит вершины, включенные в дерево кратчайшего пути, другой набор включает вершины, еще не включенные в дерево кратчайшего пути. На каждом шаге алгоритма мы находим вершину, которая находится в другом наборе (набор еще не включен) и имеет минимальное расстояние от источника.

Ниже приведены подробные шаги, используемые в алгоритме Дейкстры для нахождения кратчайшего пути от одной исходной вершины ко всем остальным вершинам данного графа.
Алгоритм
1) Создайте набор sptSet (набор дерева кратчайших путей), который отслеживает вершины, включенные в дерево кратчайших путей, т. Е. Минимальное расстояние от источника которого рассчитывается и завершается. Изначально этот набор пуст.
2) Назначьте значение расстояния для всех вершин входного графа. Инициализируйте все значения расстояния как БЕСКОНЕЧНЫЙ. Назначьте значение расстояния как 0 для исходной вершины, чтобы она выбиралась первой.
3) Хотя sptSet не включает в себя все вершины
…. a) Выберите вершину u, которой нет в sptSet и которая имеет минимальное значение расстояния.
…. б) Включите u в sptSet .
…. c) Обновить значение расстояния всех смежных вершин u. Чтобы обновить значения расстояния, выполните итерацию по всем смежным вершинам. Если для каждой смежной вершины v сумма значений расстояния u (от источника) и веса ребра uv меньше значения расстояния v, то обновите значение расстояния v.

питон

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

  
# Библиотека для INT_MAX

import sys

  

class Graph():

  

    def __init__(self, vertices):

        self.V = vertices

        self.graph = [[0 for column in range(vertices)] 

                    for row in range(vertices)]

  

    def printSolution(self, dist):

        print "Vertex tDistance from Source"

        for node in range(self.V):

            print node, "t", dist[node]

  

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

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

    # еще не включено в дерево кратчайших путей

    def minDistance(self, dist, sptSet):

  

        # Инициализировать минимальное расстояние для следующего узла

        min = sys.maxint

  

        # Поиск не ближайшей вершины не в

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

        for v in range(self.V):

            if dist[v] < min and sptSet[v] == False:

                min = dist[v]

                min_index = v

  

        return min_index

  

    # Функция, которая реализует единый источник Дейкстры

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

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

    def dijkstra(self, src):

  

        dist = [sys.maxint] * self.V

        dist[src] = 0

        sptSet = [False] * self.V

  

        for cout in range(self.V):

  

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

            # множество вершин, еще не обработанных.

            # u всегда равен src в первой итерации

            u = self.minDistance(dist, sptSet)

  

            # Поместите вершину минимального расстояния в

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

            sptSet[u] = True

  

            # Обновить значение dist соседних вершин

            # выбранной вершины, только если текущий

            # расстояние больше нового расстояния и

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

            for v in range(self.V):

                if self.graph[u][v] > 0 and \

                     sptSet[v] == False and \

                     dist[v] > dist[u] + self.graph[u][v]:

                    dist[v] = dist[u] + self.graph[u][v]

  

        self.printSolution(dist)

  
# Драйверная программа

g = Graph(9)

g.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(0);

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

Выход:

Vertex tDistance from Source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14

Пожалуйста, обратитесь к полной статье об алгоритме кратчайшего пути Дейкстры | Жадный Алго-7 для более подробной информации!

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

Программа Python для алгоритма кратчайшего пути Дейкстры | Жадный Алго-7

0.00 (0%) 0 votes