Модификация Bellman-Ford для поддержки веса второго края

Это можно сделать с помощью небольшой модификации Bellman-Ford.
Как обычно, внешний цикл будет работать не более N-1 раз, где N — количество вершин.

Вместо того, чтобы хранить расстояние до вершины от источника, вам нужно будет хранить как расстояние, так и время для каждой вершины. (обозначается dist а также time ниже)

Внутренний цикл будет немного изменен:

1. Итерировать по всем вершинам.
2. Для каждой вершины v итерируйте ее соседей.

3. Для каждого соседа u: (Tmax — максимально допустимое время)

   if (dist[v] + cost_of_edge[v -> u] < dist[u]) then
   if (time[v] + time_of_edge[v -> u] < Tmax) then
   dist[u] = dist[v] + cost_of_edge[v -> u]
   time[u] = time[v] + time_of_edge[v -> u]
   end if
   end if
   else if (dist[v] + cost_of_edge[v -> u] == dist[u]) then
   if (time[v] + time_of_edge[v -> u] < time[u]) then
   time[u] = time[v] + time_of_edge[v -> u]
   end if
   end if
   

Первое условие, если оно похоже на нормальную Беллмана — Форда: пытается найти минимальное расстояние до u, в то же время обеспечивая время, необходимое для достижения u не более чем Tmax.

Второе, если условие новое: скажем, есть путь P от источника до u со стоимостью dist[u] и занимает время time[u] быть пройденным. Теперь скажем, мы находим другой путь P' которая имеет такую ​​же стоимость dist[u] но занимает меньше времени, чем time[u] — мы хотим затем выбрать этот путь, потому что это позволит нам достичь большего количества вершин из u,

Допустим, мы не выбираем путь P' но выбирай P вместо этого, в этом случае, далее в алгоритме может быть путь от u скажем, в другую вершину x, который мы не можем рассмотреть из-за нехватки времени. Но возможно, можно рассмотреть этот путь, если путь P' выбирается с учетом времени, необходимого для прохождения P' < время, необходимое для прохождения P,