кратчайший путь с двумя переменными
Поэтому я пытаюсь использовать модифицированный алгоритм Беллмана Форда, чтобы найти кратчайший путь от начальной до конечной, но я не могу пройти определенное расстояние. Итак, дан график с ребрами:
0 1 100 30
0 4 125 50
1 2 50 250
1 2 150 50
4 2 100 40
2 3 90 60
4 3 125 150
Если каждая строка представляет ребро, а первое значение — начальная вершина, второе значение — конечная вершина, третье — стоимость, а четвертое — расстояние.
С кодом, который у меня есть сейчас, когда я пытаюсь найти самый дешевый путь от 0 до 3, не превышая 140, он выдает 0 (по умолчанию, когда путь не найден) вместо 340 (стоимость самого дешевого пути). Любые предложения о том, как изменить мой код.
Просто скопирую код ниже, потому что этот сайт не позволяет мне делать что-то еще.
static void BellmanFord(struct Graph *graph, int source, int ending, int max){
int edges = graph->edgeCount;
int vertices = graph->verticesCount;
int* money = (int*)malloc(sizeof(int) * vertices);
int* distance = (int*)malloc(sizeof(int) * vertices);
for (int I = 0; I < vertices; I++){
distance[I] = INT_MAX;
money[I] = INT_MAX;
}
distance[source] = 0;
money[source] = 0;
for (int I = 1; I <= vertices - 1; ++I){
for int j = 0; j < edges; ++j){
int u = graph->edge[j].Source;
int v = graph->edge[j].Destination;
int Cost = graph->edge[j].cost;
int Duration = graph->edge[j].duration;
if ((money[u] != INT_MAX) && (money[u] + Cost < money[v])){
if (distance[u] + Duration <= max){
money[v] = money[u] + Cost;
distance[v] = distance[u] + Duration;
}
}
}
}
if (money[ending] == INT_MAX) cout << "0" << endl;
else cout << money[ending] << endl;
}
Пожалуйста помоги! Это, наверное, не так сложно, но финалы меня напрягают
Решение
Эта проблема, известная как «ограниченный кратчайший путь» Проблема гораздо сложнее решить, чем эта. Приведенный вами алгоритм не решает его, он только может быть лови решение, только по счастливой случайности, согласно структуре графа.
Когда этот алгоритм применяется на графике, который вы предоставляете, с max-distance = 140не может найти решение, которое 0-->1-->2-->3 (используя край 1 2 150 50) общей стоимостью 340 и расстоянием 140.
Мы можем наблюдать причину сбоя, регистрируя обновления узлов, когда они обновляются, и вот результат:
from node toNode newCost newDistance
0 1 100 30
0 4 125 50
1 2 250 80
4 2 225 90
Здесь алгоритм застрял и не может идти дальше, так как любой прогресс из этой точки приведет к путям, которые превышают максимальное расстояние (из 140). Как видите, узел 2 нашел путь 0-->4--2 которая является самой дешевой из узла 0 при соблюдении ограничения максимального расстояния. Но теперь любой прогресс от 2 до 3 будет превышать расстояние 140 (это будет 150, потому что 2-> 3 имеет расстояние 60).
Снова работает с max-distance=150 найдет путь 0 -> 4-> 3 со стоимостью 315 и расстоянием 150.
from node toNode newCost newDistance
0 1 100 30
0 4 125 50
1 2 250 80
4 2 225 90
2 3 315 150
Очевидно, что это не путь минимальной стоимости, который учитывает ограничение расстояния; правильный должен быть таким же (что он не смог найти) в первом примере. Это еще раз доказывает провал алгоритма; на этот раз оно дает решение, но не оптимальное.
В заключение, это не ошибка программирования или ошибка в коде, просто алгоритм не соответствует заявленной проблеме.
Другие решения
Хорошо, так прямо перед
if (money[ending] == INT_MAX) cout << "0" << endl;
Я добавил некоторый код, который заставил его работать, но мне интересно, будет ли это работать для каждого случая или его нужно немного изменить.
if (money[ending] == INT_MAX){
for (int j = 0; j < edges; ++j){
int u = graph->edge[j].Source;
int v = graph->edge[j].Destination;
int Cost = graph->edge[j].cost;
int Duration = graph->edge[j].duration;
if ((distance[u] != INT_MAX) && (distance[u] +Duration < distance[v])){
if (distance[u] + Duration <= max){
money[v] = money[u] + Cost;
distance[v] = distance[u] + Duration;
}
}
}
}