Нахождение кратчайшего пути с помощью алгоритма Флойда-Варшалла в Python с использованием Networkx

Question

Я новичок в пакете Networkx.У меня есть следующие вершины в V и созданы ребра в N. Затем я случайным образом назначил несколько чисел для представления расстояний до ребер и создал dict E для хранения информации о ребрах и расстояниях.Я хочу найти кратчайший путь для каждой пары узлов, используя алгоритм Флойда-Варшалла.Я искал, чтобы найти некоторые примеры, но не смог в конечном итоге увидеть тот, который я могу легко реализовать.Итак, я начал с изучения того, как создать граф с помощью пакета «networkx».

import networkx as nx
import numpy as np
np.random.seed(0)
V = [333092, 467979, 177073, 164786, 178581]
N = [(i,j) for i in V for j in V if i!=j]
E = {}
Elist = list(np.random.randint(low=10, high = 50, 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, поэтому не стоит ожидать правильного решения.Но я просто не мог понять, как ввести nx.floyd_warshall ().

G=nx.Graph()
G.add_nodes_from(V)
for i in range(len(N)):
    G.add_edge(N[i][0], N[i][1])
nx.floyd_warshall(G)

Answer 1

Похоже, вы правильно вводите входные данные для nx.floyd_warshall (по крайней мере, для того, чтобы считать график невзвешенным), но я подозреваю, что вам может быть интересно узнать, как работать с весами.Вот пример, в котором я дал каждому ребру случайный вес, ключ которого равен 'distance'.

import networkx as nx
import numpy as np
import random
np.random.seed(0)
V = [333092, 467979, 177073, 164786, 178581]
N = [(i,j) for i in V for j in V if i!=j]
G=nx.Graph()
G.add_nodes_from(V)
for i in range(len(N)):
    G.add_edge(N[i][0], N[i][1], distance = random.random())
path_lengths=nx.floyd_warshall(G, weight='distance')
print(path_lengths[333092][467979])
>0.5257894083921129

path_lengths (то, что я назвал результатом nx.floyd_warshall), по сути, словарьсловарей.path_lengths[u][v] - это кратчайшая длина пути от u до v.

Обратите внимание, что по умолчанию для weight установлено значение weight='weight', поэтому, если этот ключ определен, он будет использоваться, если вы не скажетеиначе.Если не определен вес, то он обрабатывает каждое ребро как вес 1.