2

Здравствуйте, интересует реализация алгоритма расчета кратчайшего пути в метро. В голове алгоритм есть, но реализовать пока толкого не получается. Буду крайне благодарен за исходники или подсказки на эту тему. Спасибо!

9
  • Расскажите нам, как вы видите алгоритм "в голове", а мы постараемся помочь в реализации. Вообще, задача сводится к поиску кратчайшего пути на взвешенном ориентированном графе, где веса - расстояние между станциями или время пути между ними. 20 ноя 2013 в 10:32
  • В голове сумбур, даже незнаю как описать. Взять массив каждой ветки, идентифицировать его станциями, указать где они пересекаются, а дальше пока остановился. 20 ноя 2013 в 11:28
  • 3
    Не-не-не, всё не просто. Вы должны учитывать время пересадок и расписание поездов. Это не просто поиск кратчайшего пути в графе. Представьте себе, что из A в B можно доехать за 1 минуту прямо, но метро по этой линии ходит раз в полчаса. А можно с пересадкой через C, поезда из A в C и из C в B ходят каждые пять минут, и дорога занимает по три минуты. Тогда оптимальный маршрут зависит от того, скоро ли придёт прямой поезд.
    – VladD
    20 ноя 2013 в 11:41
  • 1
    Да, сразу видно, кто про метро только в книжках читал :D 20 ноя 2013 в 11:56
  • 1
    По-моему, если учитывать расписание, надо найти все маршруты до конечной станции, а потом рассчитать время каждого маршрута исходя из расписания движения поездов... Ах да, ещё же есть время между переходами со станции на станцию :) 20 ноя 2013 в 13:54

2 ответа 2

1

Если время поджимает, то я рекомендую вам выбрать простейшую модель, а именно:

  1. Граф неориентированный.
  2. Длины всех ребер одинаковые.
  3. Пересадки происходят мгновенно, группы пересадочных станций "склеены".

Подготовка

Тут надо будет поработать руками. Берете схему метро и нумеруете станции от 0 до N - 1, где N -- общее число станций, порядок не важен. Потом записываете все перегоны между станциями, которые и будут ребрами нашего графа. Каждый перегон описывается парой чисел. Записываете всю эти данные в файлик. Формат файла можно выбрать такой:

<число вершин> <число ребер>
<начало ребра 1> <конец ребра 1>
...
<начало ребра N> <конец ребра N>

Представление графа в памяти

В этой задаче подойдет представление в виде списков смежности, а так как граф в процессе не модифицируется, то реализовать его можно через std::vector<std::vector<int>>.

Загрузка графа

Загрузить граф из файла можно так:

std::ifstream data('graph.txt');
int n;
data >> n;
std::vector<std::vector<int>> graph(n);
int e;
data >> e;
for (int i = 0; i < e; ++i) {
    int a, b;
    data >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
} 

Поиск расстояний

Из-за того, что все ребра графа имеют одинаковую длину, кратчайшие расстояния в нем можно искать поиском в ширину. По ссылке http://e-maxx.ru/algo/bfs есть реализация.

-1

Топологическая сортировка +

A - Матрица смежности. B - матрица того же размера, что и А

for(int i = 0; i < N; i++)
  for (int k = i + 1; k < N; ++k)
    for (int j = k + 1; j < N; ++j)
      if (a[i][j] > a[i][k] + a[k][j])
      {
        a[i][j] = a[i][k] + a[k][j];
        b[i][j] = k;
      }

В итоге, А - матрица кратчайших расстояний, B - матрица восстановления путей

5
  • 3
    Хотел бы я посмотреть на лица пользователей Яндекс.Метро, где использовался бы такой подход. 20 ноя 2013 в 12:26
  • @Котик_хочет_кушать, уверен, что подход иной (скорее всего какая-то разновидность волнового алгоритма), но думаете лица успеют вытянуться (там всего 190 станций)?
    – avp
    20 ноя 2013 в 13:10
  • Если можно, расписать как все это изобразить кодом на C/C++, курсовая горит( Буду очень благодарен. 20 ноя 2013 в 15:25
  • 4
    @Aleksey-cda: Где ж вы раньше-то были? Вы взяли себе довольно сложную курсовую, за 5 минут вам её никто не напишет, а больше времени немногие захотят потратить. Вы бы сначала алгоритм точно придумали и описали.
    – VladD
    20 ноя 2013 в 15:35
  • @rekrut, почитайте внимательно, что такое топологическая сортировка. Она не дает кратчайших расстояний, даже если все ребра единичной длины.
    – dzhioev
    23 окт 2015 в 3:14

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.