Существует ли алгоритм удовлетворяющий моим требованиям

@nailman · Регистрация: 24.10.2012

Студворк — интернет-сервис помощи студентам

Необходим алгоритм нахождения всех кратчайших путей (как алгоритм Флойда), но только не по одной статичной величине например расстояние или одна стоимость между соседними пунктами (из пункта А один путь в В, между А и В нет иных маршрутов), а по нескольким (из пункта А множество путей в В, между А и В нет иных маршрутов).

Например 5 поездов едут в разное время по разным но пересекающимся маршрутам маршруту А В С , А Р С , А С , К С, А В К Р С, и все преодолевают маршрут за разное время. задача найти все маршруты из Р в С (прямые и с пересадкой) и сортировать их в порядки меньшего прибывания в пути.

Знаю как решить её интуитивным перебором (на мой взгляд долго и не эффективно).
Алгоритмом Флоида не понимаю как решить, ибо там есть ограничение в матрице (в одной ячейке один вес, а записав минимальный мы не получим в итоге всё множество).

Хотелось бы знать существует ли готовый оптимальный и эффективный алгоритм для сей задачи.

@Igor3D · 04.01.2014, 18:43

Я бы просто "вырезал" ребра, перенося их в др граф напр

- заносим A (исходную вершину) в список/контейнер "источников". Удаляем все ребра входящие в A, переносим все исходящие из A в новый граф и записываем их в контейнер источников

Каждое ребро/вершина может быть добавлено в "источники" только 1 раз. В результате новый граф будет иметь только ребра входящие в маршрут A-B. Обрезаем вершины из которых ничего не исходит. Выливаем новый граф в контейнер путей, сортируем. Все

@salam · 05.01.2014, 21:03

Сообщение от nailman

задача найти все маршруты из Р в С (прямые и с пересадкой) и сортировать их в порядки меньшего прибывания в пути.

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

@Qwertiy · 10.01.2014, 13:11

Рассматривать маршруты поездов как вершины нового графа и соединять их ребром, если возможна пересадка. А там уже что-то искать. Годится?

@Igor3D · 10.01.2014, 19:26

Лучше объяснить так: построить новый граф в котором каждая вершина входит хотя бы в один маршрут (подробности выше). А дальше просто ДПФ (если я правильно употребляю этот термин) - ну то есть "идем и идем не наступая на 1 ребро дважды". А поскольку вершина в путь входит - значит и "придем". Единственная (небольшая) трудность - петли.

@salam · 10.01.2014, 20:27

ДПФ - это дискретное преобразование Фурье) "идем-идем" - это, вероятно, было описание dfs-а.

@Igor3D · 11.01.2014, 11:38

Сообщение от salam

ДПФ - это дискретное преобразование Фурье) "идем-идем" - это, вероятно, было описание dfs-а.

Да, спасибо - плохо запоминаю аббревиатуры

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .

@nailman 0 / 0 / 0 Регистрация: 24.10.2012 Сообщений: 9

	Существует ли алгоритм удовлетворяющий моим требованиям 04.01.2014, 17:21. Показов 643. Ответов 6 Метки нет (Все метки) Необходим алгоритм нахождения всех кратчайших путей (как алгоритм Флойда), но только не по одной статичной величине например расстояние или одна стоимость между соседними пунктами (из пункта А один путь в В, между А и В нет иных маршрутов), а по нескольким (из пункта А множество путей в В, между А и В нет иных маршрутов). Например 5 поездов едут в разное время по разным но пересекающимся маршрутам маршруту А В С , А Р С , А С , К С, А В К Р С, и все преодолевают маршрут за разное время. задача найти все маршруты из Р в С (прямые и с пересадкой) и сортировать их в порядки меньшего прибывания в пути. Знаю как решить её интуитивным перебором (на мой взгляд долго и не эффективно). Алгоритмом Флоида не понимаю как решить, ибо там есть ограничение в матрице (в одной ячейке один вес, а записав минимальный мы не получим в итоге всё множество). Хотелось бы знать существует ли готовый оптимальный и эффективный алгоритм для сей задачи. 0

@Igor3D 1968 / 824 / 115 Регистрация: 01.10.2012 Сообщений: 4,869 Записей в блоге: 2
	04.01.2014, 18:43
	Я бы просто "вырезал" ребра, перенося их в др граф напр - заносим A (исходную вершину) в список/контейнер "источников". Удаляем все ребра входящие в A, переносим все исходящие из A в новый граф и записываем их в контейнер источников Каждое ребро/вершина может быть добавлено в "источники" только 1 раз. В результате новый граф будет иметь только ребра входящие в маршрут A-B. Обрезаем вершины из которых ничего не исходит. Выливаем новый граф в контейнер путей, сортируем. Все 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	10.01.2014, 13:11
	Рассматривать маршруты поездов как вершины нового графа и соединять их ребром, если возможна пересадка. А там уже что-то искать. Годится? 0

@Igor3D 1968 / 824 / 115 Регистрация: 01.10.2012 Сообщений: 4,869 Записей в блоге: 2
	10.01.2014, 19:26
	Лучше объяснить так: построить новый граф в котором каждая вершина входит хотя бы в один маршрут (подробности выше). А дальше просто ДПФ (если я правильно употребляю этот термин) - ну то есть "идем и идем не наступая на 1 ребро дважды". А поскольку вершина в путь входит - значит и "придем". Единственная (небольшая) трудность - петли. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	10.01.2014, 20:27
	ДПФ - это дискретное преобразование Фурье) "идем-идем" - это, вероятно, было описание dfs-а. 0