Есть ли функция, которая находит кратчайший путь между двумя узлами?

Question

Используя python, есть функция, которая позволяет мне найти кратчайшее расстояние между двумя узлами в графе networkx. Сама функция не может быть от networkx. По сути, я спрашиваю, есть ли альтернативная функция для networkx.shortest_path_length () без фактического использования NetworkX. Я посмотрел на исходный код, и он также имеет функции NX.

Answer 1

Да, есть, Алгоритм Дейкстры . Алгоритм создает дерево кратчайших путей от начальной вершины, источника, ко всем остальным точкам графа.

def dijkstra(self, src): 

    dist = [sys.maxint] * self.V 
    dist[src] = 0
    sptSet = [False] * self.V 

    for cout in range(self.V): 
        u = self.minDistance(dist, sptSet) 
        sptSet[u] = True

        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)