Возможно ли эту задачку решить на Python?
Всем привет, у меня есть вопрос. Преподаватель сказал, что эту задачку невозможно решить на Пайтоне. Вот задача:
Определите длину кратчайшего пути между пунктами B и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Возможно ли сделать эту задачу на Пайтоне? И если да, можете скинуть решение и объяснить мне как вы это сделали.
Ответы (1 шт):
Делаю за вас задание только потому, что мне полезно было освежить знание NetworkX, так то я сам почти с нуля это по его документации написал и по другим ответам на SO:
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from((('A','B',3),('A','C',7),('A','F',2)))
G.add_weighted_edges_from((('C','D',3),('C','E',1)))
G.add_weighted_edges_from((('D','E',1),('D','F',2)))
pos = nx.spring_layout(G)
nx.draw_networkx(G,pos)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)
print(nx.dijkstra_path(g, 'B', 'C'))
print(nx.dijkstra_path_length(g, 'B', 'C'))
Вывод:
['B', 'A', 'F', 'D', 'E', 'C']
9
Ну, судя по картинке, всё правильно. Короткий путь B->A->C весит 10, а найденный алгоритмом Дейкстры длинный путь весит 9.
А если вам надо вообще без библиотек, то это вы уже дальше сами. По идее алгоритм Дейкстры не сложный в реализации.