Здравствуйте всем!
Позвольте попросить у многоуважаемых участников сообщества помощи. В общем, задача состоит в следующем:
Есть карта автомобильных дорог, скажем, Украины. Вопрос: как найти кратчайший путь, например, из Днепропетровска в Ужгород? Можно, конечно, перебрать все возможные пути и выбрать минимальный из них, но тогда получаются кучи заведомо неверных вариантов... К слову, зачем ехать из Днепра в Ужгород через Донецк, конечно, для бешеной собаки собсно и 7 верст не крюк, и все же, это около шестисот лишних километров? Плюс ко всему, надо еще учесть такой вариант, что на кратчайшом пути, возможно что-то вроде ремонта дороги или движение перекрыто и целесообразнее поехать обходным путем и т.д.
Вот как задать это дополнительное условие (про ремонт дороги и перекрытость движения)?
Игры разума натолкнули на мысль, что кратчайший путь ищется по алгоритму Дейкстры, но что с этим делать дальше, непонятно :(
Спасибо заранее за помощь.
// =^_^=
