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

Question

У меня есть граф, допустим, из пяти вершин. И мне нужно найти кратчайший путь из одной вершины в другую по Алгоритму Флойда-Уоршела.
Но проблема вот в чем:
Мне нужно покрасить этот путь в другой цвет в графе.
А для этого мне нужен список всех ребер которые входят в кратчайший путь. То есть, мне нужно получить вот такой список: result = [[0, 2], [2, 1]]

Пример на фото:

Answer 1

Тьфу, блин, после ответа решил заглянуть в networkx.floyd_warshall, а там же есть predecessors in the shortest path и reconstruct_path

Заведите матрицу такого же размера, и при выборе минимума в самом внутреннем цикле Флойда-Уоршелла (псевдокод) записывайте туда (в m[i,j]) номер вершины k, соответствующий текущему этапу - переменной самого внешнего цикла. Ведь внешний цикл отвечает за то, чтобы улучшить матрицу лучших путей, если использовать k-ю вершину (до этого она не применялась).

Таким образом, после работы алгоритма для пары вершин a,b мы будем знать одну из вершин c, через которую проходит лучший путь. Аналогично найдём внутренние вершины для пар a,c и a,b, повторим рекурсивно до нахождения полного пути.

Answer 2

Мне данная задача показалась интересной и поэтому я решил сделать рабочий пример, который, возможно, окажется полезным будушим посетителям SO.

import networkx as nx

G = nx.DiGraph()

G.add_weighted_edges_from([
    ('s', 'u', 10), ('s', 'x', 5), ('u', 'v', 1), ('u', 'x', 2), 
    ('v', 'y', 1), ('x', 'u', 3), ('x', 'v', 5), ('x', 'y', 2), 
    ('y', 's', 7), ('y', 'v', 6)])

# расчет кратчайших путей для ВСЕХ пар вершин
predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
# кратчайший путь от вершины [s] к вершине [v]
shortest_path_s_v = nx.reconstruct_path('s', 'v', predecessors)
# список ребер кратчайшего пути
edges = [(a,b) for a,b in zip(shortest_path_s_v, shortest_path_s_v[1:])]
# список всех весов ребер
weights = nx.get_edge_attributes(G, 'weight')
# позиции вершин для визуализации графа
#pos = nx.spring_layout(G)
pos = nx.circular_layout(G)
# рисуем граф
nx.draw_networkx(G, pos=pos)
# рисуем веса ребер
nx.draw_networkx_edge_labels(G, pos, edge_labels=weights)
# рисуем кратчайший путь: [s] -> [v]
nx.draw_networkx_edges(G, pos=pos, edgelist=edges, edge_color="r", width=3)
# заголовок графика
title = "Shortest path between [{}] and [{}]: {}"\
        .format("s", "v", " -> ".join(shortest_path_s_v))
plt.title(title)

БЛОГ НА HUSL

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

Ответы (2 шт):