Алгоритмические задачи

Задачи о кратчайших путях.

1. Путь с наименьшим числом дуг. Пусть задан произвольный граф . Требуется построить такой путь, соединяющий две заданные вершины и , который содержит наименьшее число дуг (путь кратчайшей длины, если считать, что длины всех дуг одинаковы).

Если граф содержит небольшое число вершин и дуг, а задачу решает человек, то искомый путь может быть непосредственно «увиден», т. е. найден без применения каких-либо явно осознаваемых правил. При значительном количестве вершин и дуг в графе возникает необходимость в четком описании способа решения задачи.