Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда

курсовая работа

2.1 Задача поиска выделенного кратчайшего пути

Каждой дуге (x,y) исходного графа G поставим в соответствие число a (x,y). Если в графе G отсутствует некоторая дуга (x,y), положим a (x,y) =. Будем называть число a (x,y) длиной дуги (x,y), хотя a (x,y) можно также интерпретировать как соответствующие затраты или соответствующий весовой коэффициент. Определим длину пути как сумму длин отдельных дуг, составляющих этот путь.

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

Рассмотрим актуальность данной задачи в реальной жизни на примере.

Предположим, что вы хотите проехать из Бостона в Лос-Анджелес, используя магистральные шоссейные дороги, соединяющие различные штаты. Как выбрать кратчайший маршрут?

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

Делись добром ;)