Как называется этот алгоритм? (SSSP) - PullRequest
Новая
       117

Как называется этот алгоритм? (SSSP)

3 голосов
/ 14 июля 2020

Наблюдение: для каждого узла мы можем повторно использовать его минимальный путь к месту назначения, поэтому нам не нужно его пересчитывать (dp). Кроме того, как только мы обнаруживаем цикл, мы проверяем, отрицательный ли он. Если это не так, это не повлияет на наш окончательный ответ, и мы можем сказать, что он не подключен к месту назначения (независимо от того, подключен он или нет).

Псевдокод:

  • Указаны исходный узел u и целевой узел v

  • Инициализировать целочисленный массив dp, в котором хранится минимальное расстояние до конечного узла относительно исходного узла. dp [v] = 0, все остальное бесконечно

  • Инициализировать логический массив onPath, в котором хранится, находится ли текущий узел на рассматриваемом нами пути.

  • Инициализировать логический массив посещений, который отслеживает, был ли пройден текущий путь (изначально все ложно)

  • Инициализировать предварительный массив int, который хранит предварительное значение узла. (предварительный [u] = 0)

  • функция возврата (u). 

int function(int node){

   onPath[node] = true;

   for each connection u of node{

      if(onPath[u]){ //we've found a cycle
         if(cost to u + tentative[node] > tentative[u]) //report negative cycle
         continue; //safely ignore
      }

      if(visited[u]){
         dp[node] = min(dp[node], dp[u]); //dp already calculated

      }else{
         tentative[u] = tentative[node] + cost to u
         dp[node] = min(function(u), dp[node])
      }

      visited[node] = true;
      onPath[node] = false;
      return dp[node];
}

Я знаю, что этот алгоритм не будет охватить случай, когда пункт назначения является частью отрицательного цикла, но, кроме того, что-то не так с алгоритмом? Если нет, как это называется?

1 Ответ

1 голос
/ 14 июля 2020

Вы не можете «безопасно игнорировать» цикл положительной суммы, потому что он может скрывать более короткий путь. Например, предположим, что у нас есть граф с дугами u->x (10), u->y (1), x->y (10), y->x (1), x->v (1), y->v (10). Кратчайший uv-путь - u->y->x->v, длиной 3.

При плохом исполнении первые три вызова выглядят как 

function(u)
    function(x)
        function(y)

Исходящие соседи y - v, что дает путь y->v длиной 10; и x, но цикл logi c подавляет рассмотрение этого ar c, поэтому y помечен как посещенный с расстоянием 10 (не 2). В результате мы упускаем кратчайший путь.

...