Конспект лекций по предмету "Теория графов"


Лекция: Алгоритм Дейкстра поиска кратчайших путей в графе

Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра . В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от некоторой вершины s к рассматриваемой вершине. Эти пометки постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации только одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от t к рассматриваемой вершине. Рассмотрим подробнее этот алгоритм.
Дан граф G = (X, A, C) со взвешенными дугами, пример которого показан на рис. 9.1 Обозначим L(хi) пометку вершины хi . Веса дуг (или ребер) даны матрицей весов (таблица 9.1).

Рис. 9.1. Граф со взвешенными дугами
Таблица 9.1. Матрица весов расстояний

с1
с3



с2




с5

с4


Рассмотрим алгоритм нахождения кратчайшего пути от вершины s к вершине t графа и более общий случай: от вершины s ко всем вершинам графа.


Не сдавайте скачаную работу преподавателю!
Данный конспект лекций Вы можете использовать для создания шпаргалок и подготовки к экзаменам.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.