Кратчайший путь от одной вершины к другой в ориентированном графе

Question

Мой график направленный и очень большой. Вершины на графике представляют города, а края - маршруты автобусных поездок из города в город. Цель состоит в том, чтобы найти путь из одной вершины в другую. Очень важно, чтобы алгоритм учитывал время передачи между автобусами.

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

Answer 1

Если вам нужно найти более одного кратчайшего пути, обратитесь к этому вопросу .

Answer 2

Я не уверен с термином передачи, но есть работа по иерархии шоссе, зависящая от времени, выполняемая многими, такими как Гольдберг, Сандерс и т.д. Для статических наборов данных размера континента они в тысячи раз быстрее и предназначены для динамических и статических сценариев.

Answer 3

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