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

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.

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

---

---