кратчайший путь с двумя переменными

Итак, я пытаюсь использовать модифицированный алгоритм Беллмана Форда, чтобы найти кратчайший путь от начальной вершины до конечной вершины, но я не могу пройти определенное расстояние. Итак, для графа с ребрами:

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;
}

Пожалуйста помоги! Это, наверное, не так уж сложно, но финалы меня напрягают.


c++ bellman-ford
person codeport    schedule 04.12.2016    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Эту проблему, известную как проблема кратчайшего пути с ограничениями, решить намного сложнее, чем эту. Предоставленный вами алгоритм не решает ее, он только может найти решение, только по счастливой случайности, в соответствии со структурой графа.

Когда этот алгоритм применяется к предоставленному вами графу с 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

Очевидно, что это не путь с минимальной стоимостью, учитывающий ограничение расстояния; правильное должно быть таким же (которое не удалось найти) в первом примере. Это еще раз доказывает несостоятельность алгоритма; на этот раз он дает решение, но не оптимальное.

В заключение, это не ошибка программирования или ошибка в коде, просто алгоритм не адекватен поставленной задаче.

person A.S.H    schedule 04.12.2016
comment
Я понимаю, что алгоритм не подходит. Я искал любые подсказки о том, как отредактировать его, чтобы он работал. - person codeport; 04.12.2016
comment
@codeport известно, что эта проблема очень сложна. Задача Google с ограничениями на кратчайший путь. Насколько мне известно, слегка модифицированный Bellman Ford не входит в число известных или возможных решений. - person A.S.H; 04.12.2016

arrow_upward
0
arrow_downward

Хорошо, прямо перед

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;
                  }
             }
       }
 }
person codeport    schedule 04.12.2016