Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.93/15: Рейтинг темы: голосов - 15, средняя оценка - 4.93
0 / 0 / 0
Регистрация: 17.08.2019
Сообщений: 7

Найти кратчайший путь

14.01.2020, 12:05. Показов 3335. Ответов 20

Студворк — интернет-сервис помощи студентам
Добрый день, знаю таких программ куча и т.д., но найти подходящую я не смог. Может у кого имеется в арсинале или знает как ее сделать, так как я в этом ноль.
Суть, есть база городов.
Пример:
Владивосток-Артем=30
Владивосток-Де-Фриз=10
Артем-Де-фриз=15
Штыково-Де-Фриз=40
Артем-Штыково=50
Штыково-Шкотово=20
Мы должны вписать: Владивосток-Шкотово. И исходя из этого нам должен построится кроткий маршрут.
Вывод выглядит следующим образом: Владивосток->Де-фриз->Штыково->Шкотово = 70км
Базу городов заполнять нужно в программе самой, а в консоле только вписываем откуда куда.

С меня кола или спрайт или т.п.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
14.01.2020, 12:05
Ответы с готовыми решениями:

Как найти кратчайший путь?
Нужно реализовать алгоритм для нахождения кратчайшего пути. На ребрах указано время прохождения улицы(переулка). Нужно найти путь по...

Найти кратчайший путь шахматного короля
Здравствуйте, имеется задача: Есть шахматное поле NxM N, M ≤ 10^9 На шахматном поле отмечено два прямоугольника размерами не менее...

Как найти НЕ Кратчайший путь в графе ?
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа: 5 1 1 2 3...

20
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
28.01.2020, 00:47
Студворк — интернет-сервис помощи студентам
Решал недавно по работе, стандартный Дейкстра
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
(def edges [["Владивосток" "Артем" 30]
            ["Владивосток" "Де-Фриз" 10]
            ["Артем" "Де-Фриз" 15]
            ["Артем" "Штыково" 50]
            ["Штыково" "Де-Фриз" 40]
            ["Штыково" "Шкотово" 20]])
 
(defn path-from-to
  "Dijkstra minimal path algorithm"
  [grid from to]
  (let [visits (loop [vertex from
                      visits {vertex {:cost 0}}]
                 (if (= vertex to) visits
                     (let [vertex-time (get-in visits [vertex :cost])
                           neighbors (->> vertex grid keys (remove #(get-in visits [% :processed?])))
                           visits* (reduce (fn [acc neighbor]
                                             (let [neighbor-time (+ vertex-time (get-in grid [vertex neighbor]))]
                                               (update acc neighbor (fn [{:keys [cost] :as val}]
                                                                      (if (and cost (< cost neighbor-time))
                                                                        val
                                                                        (assoc val :cost neighbor-time :prev vertex))))))
                                           (assoc-in visits [vertex :processed?] true)
                                           neighbors)
                           vertex* (->> visits*
                                        (remove (comp :processed? second))
                                        (safe-min-key (comp :cost second))
                                        first)]
                       (if vertex* (recur vertex* visits*) visits*))))]
    {:path-time (get-in visits [to :cost])
     :path (loop [vertex to
                  path (list vertex)]
             (if-let [prev (get-in visits [vertex :prev])]
               (recur prev (cons prev path))
               (-> path vec)))}))
 
(path-from-to (reduce (fn [acc [f t d]] (-> acc
                                            (assoc-in [f t] d)
                                            (assoc-in [t f] d))) {} edges)
              "Владивосток" "Шкотово")
Code
1
{:path-time 70, :path ["Владивосток" "Де-Фриз" "Штыково" "Шкотово"]}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
28.01.2020, 00:47

Найти кратчайший путь из вершины u в вершину v
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Как найти кратчайший путь в лабиринте?
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить. ...

Найти самый кратчайший путь в массиве
У меня есть динамический массив в котором количество строк задаётся при выполнении программы, а количество строк неизменно и равно 3. Мне...

Найти кратчайший путь, без массивов
В общем дали задачку, всей группой голову уже неделю ломаем. Суть в следующем: необходимо найти длину кратчайшего пути из M в S. По...

Найти кратчайший путь между двумя заданными пунктами
Прошу объявить общий сбор всех хакеров, нужно решить задачу на C++. У меня ВСТАЛА небольшая проблема, так как я не професси, я не могу...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
21
Ответ Создать тему
Новые блоги и статьи
Сезонность и суточность закисления почв
anaschu 04.07.2026
200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле?
kumehtar 03.07.2026
Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo
anaschu 03.07.2026
Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
rest api anylogic - выполнение модели на своём русском сайте
anaschu 02.07.2026
Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru