Извиняюсь, если на этот вопрос дан ответ в другом месте, или я не очень хорошо объясняю проблему, мне сложно сформулировать это кратко для поиска.
По сути, у меня есть полностью связанный взвешенный граф.Узлы располагаются на сетке, но ребра проходят непосредственно между каждым узлом, а их вес - это просто евклидово расстояние между узлами.Мне нужно найти кратчайший путь, который соединяет каждый узел в графе, начиная с определенного узла, но без определенного конечного узла.
Моим первым инстинктом было использование алгоритма Дейкстры для поиска путей между начальным узлом икаждый из остальных узлов, затем выбирая наименьший, но алгоритм Дейкстры не заставляет посещать каждый узел.
Затем я подумал, что могу просто выбрать наименьшее расстояние на каждом шаге, пока все узлы не будут посещены, но я не могу убедить себя в том, что такой подход всегда даст кратчайший путь.Может быть (надеюсь?) Я ошибаюсь.
Тогда я решил, что могу просто перебрать его, вычислить все возможные пути и выбрать кратчайший, но я не могу представить, что это лучший способ сделать это.,
Есть предложения?Все ценится.