Лучшие shortest-path вопросы ИТ разработчиков

  • 6 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

Найдите кратчайший путь с наименьшим количеством ребер

Мне нужно изменить алгоритм Дейкстры, чтобы при наличии нескольких кратчайших путей мне нужно было найти алгоритм с минимальным количеством ребер на пути. Я застрял на том, как использовать метод Дейкстры, чтобы найти несколько кратчайших путей, ...

Задан 18 Nov 2013, 07:01 от JacK TrocinskI
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Путь без цикла ко всем узлам

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

Задан 01 Mar 2010, 21:54 от Jon
  • 16 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Что подразумевается под диаметром сети?

Диаграмма показана наэта ссылка из "Граф с 6 вершинами и 7 ребрами, где крайняя левая вершина № 6 является листовой вершиной или подвесной вершиной.&quo...

Задан 04 Jul 2010, 12:04 от user287745
  • 7 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Как получить вершины на кратчайшем пути с помощью igraph?

я используюigraph чтобы сгенерировать матрицу кратчайших расстояний между парами вершин, но я не могу понять, как вернуть вершины. Пока что у меня есть: path_length_matrix = ig_graph.shortest_paths_dijkstra(None,None,"distance", "ALL")Я ищу ...

Задан 17 Jan 2013, 14:03 от Jamie Bull
  • 7 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

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

ентированном графе с неотрицательными весами ребер я легко могу найти кратчайший путь от u до v, используя дейкстры. Но есть ли какая-нибудь простая настройка Дейкстры, чтобы я мог найти кратчайший путь от u до v через данную вершину w. Или любые ...

Задан 06 Sep 2011, 02:19 от Pradhan
  • 2 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

кратчайший путь с одним ребром повернуть к нулю

задан неориентированный взвешенный граф G и две вершины: начальная и конечная Каков наиболее эффективный алгоритм, который находит кратчайший путь от начала до конца с возможностью превращать вес ровно одного ребра в ноль? РЕДАКТИРОВАТЬ: я знаю ...

Задан 31 Dec 2012, 18:02 от user1711001
  • 87 голосов
  • 16 ответов
  • 0 просмотров
16 ответов

Кратчайший путь рыцаря на шахматной доске

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

Задан 26 Feb 2010, 02:20 от Kyle Hughes
  • 8 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Есть ли в java индексированная очередь с минимальным приоритетом?

Мне это нужно для реализации алгоритма Дейкстры, и у меня есть своя собственная реализация, но документирование моего кода было бы проще с помощью собственны...

Задан 25 Jan 2018, 14:18 от MogsdadFatso
  • 7 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Как минимизировать общую стоимость дерева кратчайшего пути

У меня есть ориентированный ациклический граф с положительными весами ребер. Он имеет один источник и набор целей (вершины, наиболее удаленные от источника)....

Задан 08 May 2010, 03:43 от Michael
  • 15 голосов
  • 7 ответов
  • 0 просмотров
7 ответов

Эффективно найти кратчайший путь в больших графах

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

Задан 14 Jun 2010, 15:50 от Björn Lindqvist
  • 1 голос
  • 0 ответов
  • 0 просмотров
0 ответов

Кратчайший путь в «двухграфе» с ограниченным количеством изменений

Позволять'скажем, у нас есть два ориентированных и положительно взвешенных графика на одном наборе вершин (первый график представляет, например, железные...

Задан 03 Jan 2014, 11:24 от MrConfused
  • 26 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Нет, практически Флойд-Варшалл не быстрее Дейкстры для всех пар кратчайшего пути (как правило !!)

аю алгоритм Дейкстры и алгоритм Флойда-Варшалла. Я понимаю, что Дейкстра находит оптимальный маршрут от одного узла ко всем остальным узлам, а Флойд-Варшалл ...

Задан 18 Nov 2010, 07:10 от pyt
  • 4 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Как мне найти кратчайший путь, который охватывает все узлы в ориентированном циклическом графе?

Мне нужен пример кратчайшего пути ориентированного циклического графа от одного узла (он должен достигать всех узлов графа от узла, который будет входным). Пожалуйста, если есть пример, он мне нужен в C ++ или в алгоритме.

Задан 25 Apr 2009, 15:36 от Thaier Alkhateeb
  • 5 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Дейкстра и Прим создают деревья, а не дорожки, верно?

я есть серия координат графика, и мне нужно найти кратчайший односторонний путь через все из них. У меня нет заранее определенного начала / конца, но к каждой точке нужно прикоснуться только один раз, и возвращение к оптимальному началу ...

Задан 24 Jan 2011, 08:50 от stumped_coder
  • 13 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Алгоритм Дейкстры с очередью с минимальным приоритетом

Я пытаюсь реализовать алгоритм Дейкстры с приоритетной очереди, но я не могуне понимаю, как это работает. Я читаю много руководств в Интернете, но могуЯ не п...

Задан 19 Aug 2013, 11:11 от giacomotb
  • 6 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

график - Как найти минимальный направленный цикл (минимальный общий вес)?

Вот акциз: Let G be a weighted directed graph with n vertices and m edges, where all edges have positive weight. A directed cycle is a directed path that...

Задан 04 May 2012, 22:49 от Jackson Tale
  • 26 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

(V * logV + E))

кратчайший путь между двумя точками на графике - это вопрос классических алгоритмов с множеством хороших ответов (Алгоритм Дейкстры [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm], ...

Задан 26 Aug 2011, 17:56 от templatetypedef
  • 101 голос
  • 12 ответов
  • 0 просмотров
12 ответов

Почему алгоритм Дейкстры не работает для отрицательных весовых граней?

Может кто-нибудь сказать мне, почему алгоритм Дейкстры для кратчайшего пути с одним источником предполагает, что ребра должны быть неотрицательными. Я говорю только о ребрах, а не о циклах отрицательного веса.

Задан 31 Oct 2012, 13:41 от Madu
  • 11 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Как найти кратчайший путь в динамической ситуации

Несколько дней назад кто-то спросил меня: если у нас есть какие-то агенты в нашей среде, и они хотят перейти от своих источников к месту назначения, как мы можем найти общий кратчайший путь для всех них, чтобы у них не было конфликтов во время их ...

Задан 18 Feb 2012, 14:05 от Saeed Amiri
  • 9 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Алгоритм k-кратчайшего (альтернативного) пути, реализации Java

Не могли бы вы порекомендовать любую библиотеку Java, которая реализует алгоритм k-кратчайшего - & gt; В поисках альтернативных путей, не единственного кратч...

Задан 07 Oct 2012, 22:49 от Martin V.
  • 4 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Нахождение кратчайшего пути с помощью запроса SPARQL

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

Задан 17 Jan 2013, 20:57 от Abraham D Flaxman
  • 0 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

кратчайший путь от цели к корню в ориентированном графе с циклами python

Я хочу найти кратчайший путь отgoal вroot работая в обратном направлении Мой вклад дляroot является{'4345092': ['6570646', '40586', '484']} Мой вклад дляgoal является{'886619': ['GOAL']} Мой вклад дляpath_holder является входом, но он ...

Задан 03 Dec 2013, 13:09 от Liondancer
  • 4 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Модификация алгоритма кратчайшего пути (маршрут от узла к себе)

Я применяю алгоритм кратчайшего пути для всех пар (Флойд-Воршалл [http://algowiki.net/wiki/index.php/Floyd-Warshall%27s_algorithm]) к этому ориентированному графу:альтернативный ...

Задан 23 Dec 2009, 19:10 от denchr
  • 3 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

есть ли маршрут из города А в город Б не более чем за x дней?

Я был на собеседовании в торговой фирме, мне задавали этот вопрос,Вы путешествуете по всему штату на автобусах, автобусы могут останавливаться в любых C возм...

Задан 10 Apr 2013, 22:40 от user2149873
  • 0 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Минимальное расстояние между началом и концом при прохождении должно посещать точки в лабиринте

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

Задан 22 Aug 2014, 06:43 от zero infinity
  • 6 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

«Двунаправленный Dijkstra» от NetworkX

Я только что прочитал реализацию NetworkX алгоритма Дейкстры для кратчайших путей, используя двунаправленный поиск (вэтот). Какова конечная точка этого метода?

Задан 03 Mar 2016, 18:21 от moksef
  • 13 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Алгоритм Дейкстры с очередью с минимальным приоритетом

Я пытаюсь реализовать алгоритм dijkstra с приоритетной очередью, но я не могу понять, как он работает. Я прочитал много руководств в Интернете, но я не могу понять этот алгоритм вообще. Мой вопрос: каков приоритет для каждого узла? Я думаю, что ...

Задан 19 Aug 2013, 13:11 от giacomotb
  • 1 голос
  • 1 ответ
  • 0 просмотров
1 ответ

Кратчайший путь в «двухграфе» с ограниченным количеством изменений

Допустим, у нас есть два ориентированных и положительно взвешенных графика на одном наборе вершин (первый график представляет, например, железные дороги, а второй - автобусные полосы; вершины - это автобусные остановки или железнодорожные станции ...

Задан 03 Jan 2014, 12:24 от MrConfused
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Если оптимальный путь не включает удаленный узел, это не будет затронуто. Однако, если это так, то да, вы правы, это возможно для оптимального пути изменения. И именно поэтому вы должны снова запустить алгоритм кратчайшего пути.

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

Задан 20 Jul 2011, 10:03 от LiKao
  • 3 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Как установить целевую вершину в QuickGraph Dijkstra или A *

Я использую QuickGraph версии 3.6, и я нашел функцию SetRootVertex, но не SetTagretVertex. Мне это нужно, потому что я ищу короткие пути в огромном графике, и это сильно ускорит программу Рассматриваемые условия - DijkstraShortestPathAlgorithm ...

Задан 22 Dec 2011, 16:02 от watbywbarif
  • 0 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

@pyd первым делом замените все пропущенные значения на ноль или ноль. Затем используйте приведенный выше код. Когда вы имеете дело с числами, в кадре данных не должно быть никаких dty-типов объектов.

я есть датафрейм с городами и расстоянием между другими городами от каждого города. Мой набор данных выглядит так, ДФ, From City City A City B City C City D City A 2166 577 175 City B 2166 1806 2092 City C 577 1806 653 City D 175 2092 653Я ...

Задан 06 May 2018, 05:29 от pyd
  • 9 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Алгоритм кратчайшего пути Дейкстры со стоимостью ребра

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

Задан 26 Apr 2010, 00:23 от Svisstack
  • 25 голосов
  • 6 ответов
  • 0 просмотров
6 ответов

В чем разница между алгоритмом Дейкстры и Прима?

Кто-нибудь может сказать мне разницу междуДейкстры [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm]а такжеПрима [http://en.wikipedia.org/wiki/Prim%27s_algorithm]алгоритмы? Я знаю, что делает каждый из алгоритмов. Но они выглядят одинаково ...

Задан 10 Dec 2012, 04:19 от Pradit
  • 8 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Кратчайший путь в JavaScript

Я неделями искал способ вычисления кратчайших путей в JavaScript. Я играл с книгойСтруктуры данных и алгоритмы Гронер (метко названный) вhttps://github.com/l...

Задан 11 Sep 2015, 15:28 от Tyler330
  • 7 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

Для алгоритмов кратчайшего пути я всегда выбирал C ++. Не должно быть никаких причин, по которым реализация C не была бы слишком простой, но C ++ предлагает сокращенное кодирование с контейнерами STL, которые можно использовать в начальной реализации, и только позже реализует оптимизированный алгоритм очереди, если тесты производительности и профилирование показывают, что нужно что-то иметь. лучше, чем предлагает STL.

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

Задан 23 Aug 2011, 17:51 от Eugenio
Page 1 of 2
1 2