ff78d4ec

Алгоритм Дейкстры


  1. Расстояние от s до s, конечно же, равно 0. Кроме того, это расстояние уже никогда не сможет стать меньше - ведь веса всех ребер графа у нас положительны. Таким образом:

    dist[s]:= 0; done[s]:= true; last:= s;

  2. Повторить N-1 раз следующие действия:

  1. для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:

    dist[x]:= min(dist[x], dist[last]+ sm[last,x]);

  2. среди всех непомеченных вершин найти минимум в массиве dist: это будет новая вершина last;
  3. пометить эту новую вершину в массиве done.



Содержание раздела