В чем заключается алгоритм подсчета кратчайшего пути между двумя вершинами в транспортной сети?

Алгоритм подсчёта кратчайшего пути между двумя вершинами в транспортной сети может включать следующие шаги: 2

1. Подготовительный шаг. 2 В специальную таблицу заносят номера вершин, во вторую колонку в сторону вершины «от» ставят «О» (ноль), во все другие строки записывают заведомо большое число. 2 В третьей колонке в строке вершины «от» ставят «1» (единицу) — условный знак проверки. 2
2. Выбор строки с условным знаком проверки. 2 Если такой строки нет, переходят к следующему шагу. 2 В противном случае зачёркивают условный знак проверки и перебирают все связи выбранной вершины с другими вершинами. 2 Для каждой из таких вершин рассчитывают вариант расстояния от вершины «от». 2
3. Сравнение полученных расстояний. 2 Полученное расстояние сравнивают с имеющимися в строке с вершиной, для которой рассчитывают вариант расстояния. 2 Если полученное расстояние меньше имеющегося, то в строке с вершиной зачёркивают значение, записывают новое расстояние, в третью колонку записывают условный знак проверки, в четвёртую колонку — номер предыдущей вершины. 2
4. Определение кратчайшего маршрута следования. 2 Начиная с вершины «до», перечисляют номера предыдущих вершин, то есть получают запись маршрута в обратном порядке. 2 «Перевернув» запись, приходят к маршруту следования по кратчайшему пути. 2

Для расчёта кратчайших расстояний также используют алгоритмы Дейкстры, А*, Беллмана–Форда, Джонсона и другие. 34