кратчайший путь с более чем 2 Точками, но фиксированный Порядок

#graph-theory #dijkstra #graph-algorithm #computer-science-theory

#теория графов #dijkstra #граф-алгоритм #информатика-теория

Вопрос:

во-первых, пожалуйста, извините мои плохие знания английского.

У меня следующая проблема: я должен найти кратчайший путь между более чем 2 точками в фиксированном порядке (например, A -> D -> F). Я знаком с алгоритмом Дейкстры. Но этот вычисляет только кратчайший путь между двумя точками. И я также слышал о чайной ложке, но это, похоже, тоже не подходит. Потому что нет фиксированного порядка. Я уже искал в Интернете свою Проблему, но, возможно, это не очень популярная проблема, или я использовал неправильные ключевые слова.

Тем не менее, должно существовать решение, потому что существует множество планировщиков маршрутов, которые успешно предоставляют эту функцию.

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

большое вам спасибо за вашу помощь! искренне ваш, Анджело

// редактировать О, это очень смущает. Кажется, я слишком долго думал, поэтому мне не удалось описать реальную проблему. Это так: есть несколько билетов, которые можно использовать только с самого начала.

T1: A -> B (стоит 50) T2: B -> C (стоит 50) T3: A -> B -> C (стоит 80) Данный маршрут A -> B -> C

Теперь вы видите, если мы будем рассматривать данный маршрут как две отдельные задачи, общая стоимость составит 100, но, очевидно, билет T3 является лучшим решением.

1. Итак, просто для ясности, вы всегда знаете промежуточные переходы? Вашим первым примером был A-> D-> F. Есть ли какая-то причина, по которой вы бы запланировали маршрут A-> B-> D-> F?

2. да, существует заданный маршрут, подобный примеру A -> D -> F, но график, который получается из заданных билетов, больше. Между A и D. Может отсутствовать прямое ребро, или, если оно есть, возможно, маршрут A -> B -> D стоит меньше, чем прямой путь.

Ответ №1:

Если некоторые точки исправлены, а другие нет (это означает, что пользователь хочет перейти от A->D->F , но график означает, что им, возможно, придется это сделать A->B->C->D->E->F ), это стандартная проблема. Либо вы заботитесь о ADF порядка, либо нет (это может быть AFD). В первом случае это просто два пути ( A->D D->F ), которые вы вычисляете независимо. Во втором случае это больше похоже на TSP.

Ответ №2:

Вы можете найти кратчайший путь между A и D, затем кратчайший путь между D и F и т.д. Применение алгоритма Дейкстры несколько раз для каждой пары узлов.