2

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

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

3
  • Можете привести в вопросе матрицу смежности графа в виде текста/CSV ? 26 апр 2020 в 21:59
  • Не совсем понятно зачем использовать алгоритм Флойда-Уоршела если искать нужно кратчайший путь для пары вершин?? Этот алгоритм предназначен для поиска кратчайших путей между всеми парами вершин графа 27 апр 2020 в 7:13
  • @MaxU знаю, но преподаватель хочет, чтобы еще в графе показался другим цветом путь
    – Ivan
    27 апр 2020 в 9:55

2 ответа 2

5

Мне данная задача показалась интересной и поэтому я решил сделать рабочий пример, который, возможно, окажется полезным будушим посетителям 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)

введите сюда описание изображения

1
  • 1
    спасибо огромное!!! Мне очень помогло ваше решение!!!
    – Ivan
    27 апр 2020 в 20:50
2

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


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

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

7
  • спасибо @MBo, я понял, что вы имеете введу, но реализовать в коде не получаеться
    – Ivan
    27 апр 2020 в 9:58
  • А Вы используете networkx?
    – MBo
    27 апр 2020 в 10:01
  • да, и Matplotlib
    – Ivan
    27 апр 2020 в 10:11
  • 1
    Ну ведь там есть reconstruct_path для этой цели, если я правильно понял
    – MBo
    27 апр 2020 в 10:12
  • Ага, спасиб, нашел в документации
    – Ivan
    27 апр 2020 в 10:16

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.