1. Главная
  2. Библиотека
  3. Информационные технологии
  4. Определите, чему будет равно значение P[2] в алгоритме Дейкстры, если источником является вершина c (узел а – 1-ый в нумер...

Определите, чему будет равно значение P[2] в алгоритме Дейкстры, если источником является вершина c (узел а – 1-ый в нумерации узлов, … узел e – 5-ый)

«Определите, чему будет равно значение P[2] в алгоритме Дейкстры, если источником является вершина c (узел а – 1-ый в нумерации узлов, … узел e – 5-ый)»
  • Информационные технологии

Условие:

Определите, чему будет равно значение P[2] в алгоритме Дейкстры, если источником является вершина c (узел а – 1-ый в нумерации узлов, … узел e – 5-ый)

Решение:

Алгоритм Дейкстры (Dijkstras algorithm) алгоритм на графах, находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса.

Шаг 0:

Установим расстояние для начальной вершины d(3)=0

Шаг 1:

Непомеченные вершины V={1;2;3;4;5;}

Минимальные расстояния до непомеченных вершин d={;;0;;;}

Убираем вершину 3 c наименьшим расстоянием 0 из множества V

Установим v...

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет