Алгоритм Belman-Ford в массиве 2d

Ответ 1

Если вы знаете, как перемещаться по графику из массива, вы можете перейти к дополнительному абзацу условий. Читайте также следующий параграф.

Фактически, вы можете посмотреть на это здание, как на графике.

Вы можете видеть: (Я забыл о дверях во второй строке, извините).

Итак, как можно реализовать. Игнорируйте на данный момент дополнительное условие (зайдите в конкретную вершину перед отъездом).
Функция веса:
Пусть S[][] - массив входных затрат. Обратите внимание, что о массе края решает только вершину на конце. Не имеет значения, если оно (1, 2) -> (1,3) или (2,3) -> (1, 3). Стоимость определяется второй вершиной. поэтому функция может выглядеть так:

cost_type cost(vertex v, vertex w) {
    return S[w.y][w.x];
}
//As you can see, first argument is unnecessary.

Края:
На самом деле вам не нужно сохранять все ребра в каком-то массиве. Вы можете рассчитывать их в функции каждый раз, когда вам нужно. Соседи для вершины (x, y) являются (x+1, y), (x-1, y), (x, y+1), (x, y-1), если эти узлы существуют. Вы должны проверить это, но это легко. (Убедитесь, что new_x > 0 & new_x < max_x.) Это может выглядеть так:

//Size of matrix is M x N
is_correct(vertex w) {
    if(w.y < 1 || w.y > M || w.x < 1 || w.x > N) {
        return INCORRECT;
    }
    return CORRECT;
}

Генерация соседей может выглядеть так:

std::tie(x, y) = std::make_tuple(v.x, v.y);
for(vertex w : {{x+1, y}, {x-1, y}, {x, y+1}, {x, y-1}}) {
    if(is_correct(w) == CORRECT) {//CORRECT may be true
        relax(v, w);
    }
}

Я считаю, что он не должен брать дополнительную память для четырех ребер. Если вы не знаете std:: tie, посмотрите cppreference. (Дополнительные переменные x, y занимают больше памяти, но я считаю, что это более читаемо здесь. В вашем коде это может не отображаться.)

Очевидно, что у вас должен быть другой 2D-массив с расстоянием и (если необходимо) предшественником, но я думаю, что это понятно, и я не должен его описывать.

Дополнительное условие:
Вы хотите узнать стоимость от входа, чтобы выйти, но вам нужно посетить некоторую вершину compulsory. Самый простой способ рассчитать его - рассчитать стоимость от enter до compulsory и от compulsory до exit. (Будет два отдельных расчета.) Это не изменит большое время O. После этого вы можете просто добавить результаты.

Вам просто нужно гарантировать, что невозможно exit посетить compulsory. Это легко, вы можете просто стереть исходящие ребра из exit, добавив дополнительную строку в функцию is_correct (тогда понадобится вершка v.) Или в генерации фрагмента кода соседей.

Теперь вы можете реализовать его на основе wikipedia. У вас есть график.

Почему вы не должны слушать?
Лучше всего использовать алгоритм Белмана Форда из другой вершины. Обратите внимание, что если вы знаете оптимальный путь от A до B, вы также знаете оптимальный путь от B до A. Почему? Всегда нужно платить за последнюю вершину, и вы не платите за нее, поэтому можете игнорировать затраты на них. Отдых очевиден.
Теперь, если вы знаете, что хотите знать пути A- > B и B- > C, вы можете рассчитать B- > A и B- > C, используя однократный BF от node B и обратный путь B- > A. Это закончилось.
Вам просто нужно удалить исходящие ребра из узлов entry и exit.

Однако, если вам нужен очень быстрый алгоритм, вы должны его оптимизировать. Думаю, это для другой темы. Кроме того, похоже, что никто не заинтересован в жесткой оптимизации.
Я могу быстро добавить, просто эта небольшая и простая основа для оптимизации, что вы можете игнорировать релаксацию из соответствующих удаленных вершин. В массиве вы можете легко вычислить расстояние, так что это приятная оптимизация.
Я не упомянул хорошо известную оптимизацию, потому что я считаю, что все они находятся в случайном курсе сети.