salesman-problem

Решение задачи о коммивояджере: через полный перебор и через алгоритм двойного приближения. Тесты прилагаются.

Асимптотика алгоритма двойного приближения

Алгоритм Прима работает за O(E*log(V)), затем запускается DFS за O(V + E). Итого O(E*log(V) + V).

Name		Name	Last commit message	Last commit date
Latest commit History 3 Commits
lib/googletest		lib/googletest
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
Edge.cpp		Edge.cpp
Edge.h		Edge.h
GraphAlgorithms.cpp		GraphAlgorithms.cpp
GraphAlgorithms.h		GraphAlgorithms.h
IWeighedGraph.h		IWeighedGraph.h
ListWeighedGraph.cpp		ListWeighedGraph.cpp
ListWeighedGraph.h		ListWeighedGraph.h
MertixCompleteGraphGenerator.cpp		MertixCompleteGraphGenerator.cpp
MertixCompleteGraphGenerator.h		MertixCompleteGraphGenerator.h
README.md		README.md
main.cpp		main.cpp