У меня есть простой график вроде этого:
(v1)---(v2)---(v3)---(v10)
| | |
(v4)---(v5)---(v6)
| | |
(v7)---(v8)---(v9)
Я превращаю игровое поле в сетки, и каждая сетка является вершиной, а каждая вершина имеет вес. Теперь мне нужен алгоритм, чтобы найти наиболее взвешенный путь между одной вершиной, которая может быть одной из вершин из (v1) в (v9) , и другой вершиной (v10) .
Пример для веса вершин: Предположим, что вес каждой вершины равен 1, поэтому, если мой путь будет (v1) -> (v2) -> (v3) -> (v10) , мой вес пути будет равен 4.
Я уже использовал алгоритм BFS, чтобы найти все возможные пути, а затем вычислить вес подходящих путей (тех путей, которые заканчиваются (v10) ) между все пути. Но BFS не может найти все возможные пути для меня (возможно, BF. Однако я могу использовать для этого хитрость, но мне интересно, есть ли алгоритм, позволяющий сделать мою работу более простой и эффективной:).