Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 5.30. Уточненная структура узлов графа 
public class TNode 
{ 
public string name; // 
public TEdge[] Edge; // 
ребра 
public bool visit; 
public int x, y; // 
public int numVisit; 
public Color color; 
public int dist, oldDist; 
} 
В классе узла TNode появилось поле dist, предназначенное для хра-
нения расстояния до узла s. 
Приведем последовательность шагов для алгоритма Дейкстры при 
A
ij
≥0: 
1. Присвоение начальных значений. Положить dist(s) = 0 и счи-
тать этот узел помеченным visit(s) = true, т. е. в дальней-
шем dist(s) не изменяется. Положить dist(x
i
) = 
∞. Положить 
p = s. 
9 / 23

---

171 
2. Обновление dist. Для всех непомеченных узлов xi 
∈ Г(p) 
уточнить dist по формуле: dist(x
i
) = Min(dist(x
i
), 
dist
(p) + Ap
i
). 
3. Отметить один узел. Среди всех непомеченных узлов найти та-
кой, для которого dist(x
i
*) = Min(dist(x
i
)), и пометить его. 
4. Положить p = x
i
*. 
5. Если p = s, то путь найлен, иначе перейти к шагу 2. 
В листинге 5.31 приведена нерекурсивная функция, реализующая этот 
алгоритм. 
Листинг 5.31. Алгоритм Дейкстры 
public int Dijkst(int s, int t) 
{ 
int result; 
ClearVisit(); SetMatr(); 
int N = Nodes.Length; // 
Инициализация 
for (int i = 0; i <= N - 1; i++) 
Nodes[i].dist = 0xFFFFF; 
Nodes[s].dist = 0; VisitTrue(s); 
int p = s; 
do 
{ 
p = FindMinDist(p);
VisitTrue(p); // 
обновление и найти 
} 
while (p != t); 
result = Nodes[p].dist; 
PathToStack(s, p); 
return result; 
} 
Эта функция возвращает минимальное расстояние от узла s до узла t. 
Шаги 2 и 3 реализует функция FindMinDist() (листинг 5.32). 
10 / 23

---

172 
Листинг 5.32. Уточнение Dist и определение Min 
int FindMinDist(int p) 
{ 
int MinDist = 0xFFFFF; 
int result = 0; 
int N = Nodes.Length; 
for (int i = 0; i <= N - 1; i++) 
{ 
if (!Nodes[i].visit) 
{ 
Nodes[i].dist = Math.Min(Nodes[i].dist,
Nodes[p].dist + A[p, i]); 
if (Nodes[i].dist < MinDist) 
{ 
MinDist = Nodes[i].dist; result = i; 
} 
} 
} 
return result; 
} 
Алгоритм Дейкстры не определяет минимальный путь, т. е. последова-
тельность вершин, по которым надо пройти от s до t. Но этот путь можно 
получить с помощью рекурсивного соотношения Dist(x
i
*
) + A(x
i
*
,x
i
) = 
= Dist(x
i
), т. к. вершина x
i
*
предшествует вершине x
i
на минимальном пути. 
Эту рекурсию реализует функция PathToStack(), которая помещает вер-
шины минимального пути в стек (листинг 5.33). 
Листинг 5.33. Определение минимального пути 
void PathToStack(int s, int p) 
{ 
11 / 23

---

173 
Lib.myStack = new MyStack(); 
int N = Nodes.Length; 
while (p != s) 
{ 
Lib.myStack.Push(p); // 
положить в стек 
int i = -1; bool Ok = false; 
while ((i < N - 1) && !Ok) 
Ok = (++i != p) && (Nodes[p].dist ==
Nodes[i].dist + A[i, p]); 
p = i; 
} 
} 
На рисунке 5.12 показан результат работы алгоритма при определении 
минимального пути от вершины Node1 до Node8. В окне выведен стек с 
вершинами пути: 2, 4, 6, 9, 8. 
Рис. 5.12. Пример определения минимального пути от вершины Node1 до 
Node8
12 / 23

---

174 
Обратите внимание на то, что алгоритм не пошел из Node4 в вершину 
Node7
по пути длиной 23, более короткому, чем через Node6, и суммарно 
выиграл.