Witam.
Potrzebuje program, który w danym grafie ważonym znajduje ścieżke o najmniejszej wadze przechodzącą przez wszystkie wierzcholki. Pomoże ktoś, bo zupełnie nwm jak się za to zabrać i z czego skorzystać?
0
2
Wygląda, że chodzi Ci o MST. Wydaje mi się, że selfexplanatory pseudokod (Python), wraz z potrzebnymi strukturami danych, popełniłem tutaj:
https://github.com/lion137/Python-Graph/blob/master/minimum_spanning_tree.py
Najbardziej zrozumiałe w internecie wytłumaczenie tutaj:
.
0
Tak lion137, właśnie o to chodzi. Dziękuję.
0
Proszę bardzo. Jeśli chodzi o Javę, to polecam fantastyczną książkę: Sedgewick Wayne "Algorithms in Java". Jest również stronka: https://algs4.cs.princeton.edu/40graphs/ , oraz kurs na courserze: https://www.coursera.org/learn/algorithms-part2
1
@lion137 nie no MST to nie to samo co TSP :P Pytanie czy można odwiedzić wierzchołki więcej niż raz? Bo pewnie nie można i to Komiwojażer a nie MST.