0

Не могу понять какой алгоритм использовать.

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

объяснение (например): есть 3 маршрута (помечены разными цветами)->маршруты

надо из "1" остановки попасть в "4" остановку. для этого нам надо пересесть на "2" остановке на 2 маршрут, потом на "3" остановке пересесть на 3 маршрут и доехать до "4" остановки.

переменные: есть массив

elem1 (1)(0) = 1

elem1 (1)(1) = 2

elem1 (2)(0) = 2

elem1 (2)(1) = 3

elem1 (3)(0) = 4

elem1 (3)(1) = 3

elem [№ маршрута] [№ п\п]. то есть в 1 маршруте остановка "1" - это первая по порядку, остановка "2" - вторая по порядку. и тп.

надо смотреть маршрут и искать на нем пересечения. если пересечений нет, то берем остановку, если на ней несколько маршрутов, то переходим на следующий маршрут и ищем пересечения там. но надо найти минимальное количество пересечений между маршрутами.

вроде как надо использовать алгоритм поиска в глубину, но не простой.

3
  • 2
    Самое простое, пожалуй — поиск кратчайшего пути во взвешенном графе — типа алгоритма Дейкстры. При этом "пересадочные" вершины делятся на 2 с ребром веса 1 между ними; все остальные ребра — нулевые. В вашем примере, кстати, две пересадки...
    – Harry
    21 окт 2021 в 13:45
  • Harry, для алгоритма дейкстры нужно указывать вес для путей. а как я это сделаю? мне это и не надо
    – Max
    21 окт 2021 в 14:10
  • 2
    Все нулевые, кроме пересадок.
    – Harry
    21 окт 2021 в 14:19

0

Ваш ответ

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

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