Как получить полный путь от алгоритмов кратчайшего пути Networkx - PullRequest
Новая
       37

Как получить полный путь от алгоритмов кратчайшего пути Networkx

1 голос
/ 17 июня 2019

Я использую floyd_warshall_predecessor_and_distance функцию Networkx в Python 3, чтобы найти кратчайший путь на двунаправленном графике.Функция возвращает кратчайшее расстояние между заданными двумя узлами (если существует ребро) и частью пути.Я поясню, что я имею в виду, говоря «порция».Ниже приведены мои входные и выходные данные.

Входные данные : 

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(0)
V = [1, 2, 3, 4, 5]
N = [(i,j) for i in V for j in V if i!=j]
E = {} #Creating an empty dictionary to store the travel times from node i to j
Elist = (list(np.random.randint(low=1, high = 30, size = len(N))))
for i in range(len(N)):
    E[N[i]] = Elist[i] # (i,j) does not have to be equal to (j,i)
E[(2, 1)] = 5
E[(5, 4)] = 0
E[(2, 4)] = 20
G=nx.DiGraph()
G.add_nodes_from(V)
for i in E:
    G.add_weighted_edges_from([(i[0], i[1], E[i])])
path_lengths=nx.floyd_warshall_predecessor_and_distance(G, weight='weight')
path_lengths

Выходные данные : 

({1: {2: 1, 3: 4, 4: 5, 5: 1},
  2: {1: 2, 3: 4, 4: 5, 5: 1},
  3: {1: 3, 2: 3, 4: 5, 5: 1},
  4: {1: 4, 2: 1, 3: 4, 5: 1},
  5: {1: 4, 2: 5, 3: 4, 4: 5}},
 {1: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {1: 0, 2: 13, 3: 8, 4: 1, 5: 1}),
  2: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {2: 0, 1: 5, 3: 13, 4: 6, 5: 6}),
  3: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {3: 0, 1: 10, 2: 20, 4: 11, 5: 11}),
  4: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {4: 0, 1: 5, 2: 18, 3: 7, 5: 6}),
  5: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
              {5: 0, 1: 5, 2: 13, 3: 7, 4: 0})})

Я специально сделалпуть для (2, 4), который равен 2> 1> 5> 4. Когда я смотрю на path_lengths[0], я вижу, что для перехода от узлов 2 к 4 я остановился на 5. Далее, чтобы перейти от 2 к5, я остановился на 1. Эти два говорят мне полный маршрут, но я хочу видеть весь маршрут как вывод, например, 2: {... 4: 1, 5, ...} или {(2,4): (2,1), (1,5), (5,4)}, а не видеть его по частям, а затем объединять части в уме.Есть ли лучший пакет в Networkx, который может это сделать?Кстати, мой двунаправленный граф не содержит отрицательных весов, и график может быть довольно большим (поэтому я выбрал эту функцию).

Вот моя попытка начать: 

new = path_lengths[0]
for v in V:
    for d in V:
        if v!=d:
            if new[v][d] != v:
                new[v][d] = (new[v][d],d)
            elif new[v][d] == v:
                new[v][d] = (v,d)

Спасибо за ответы!

1 Ответ

1 голос
/ 17 июня 2019

Я нашел решение проблемы.Следующий код создает два словаря.Для paths клавиши обозначают дуги, а значения показывают последовательные дуги, которые необходимо принять для кратчайшего пути .Для shortest_distance клавиши обозначают дуги, а значения показывают самое короткое расстояние .Я оставляю это здесь для дальнейшего использования.

Вход : 

def arcs(seq, n):
    return [seq[max(i, 0):i + n] for i in range(-n + 1, len(seq))]
paths = {}; shortest_distance = {}
for v in V:
    for d in V:
        if v!=d:
            path = nx.single_source_dijkstra_path(G,v)
            paths[(v,d)] = path[d]
for i in paths:
    paths[i] = (arcs(paths[i],2)[1:-1])
    shortest_distance[(i[0],i[1])] = path_lengths[1][i[0]][i[1]]
    for j in range(len(paths[i])):
        paths[i][j] = tuple(paths[i][j])    
for i in paths:
    print(i, paths[i], shortest_distance[i])

Выход : 

(1, 2) [(1, 2)] 13
(1, 3) [(1, 5), (5, 4), (4, 3)] 8
(1, 4) [(1, 5), (5, 4)] 1
(1, 5) [(1, 5)] 1
(2, 1) [(2, 1)] 5
(2, 3) [(2, 1), (1, 5), (5, 4), (4, 3)] 13
(2, 4) [(2, 1), (1, 5), (5, 4)] 6
(2, 5) [(2, 1), (1, 5)] 6
(3, 1) [(3, 1)] 10
(3, 2) [(3, 2)] 20
(3, 4) [(3, 1), (1, 5), (5, 4)] 11
(3, 5) [(3, 1), (1, 5)] 11
(4, 1) [(4, 1)] 5
(4, 2) [(4, 1), (1, 2)] 18
(4, 3) [(4, 3)] 7
(4, 5) [(4, 1), (1, 5)] 6
(5, 1) [(5, 4), (4, 1)] 5
(5, 2) [(5, 2)] 13
(5, 3) [(5, 4), (4, 3)] 7
(5, 4) [(5, 4)] 0
...