Вопросы по теме 'dijkstra'

Почему эта реализация Дейкстры (графа) не работает?
Я сделал следующую реализацию для этой проблемы: http://www.spoj.pl/problems/SHOP/ #include<iostream> #include<stdio.h> #include<queue> #include<conio.h> #include<string.h> using namespace std; struct node {...
827 просмотров
c++ graph dijkstra
schedule 20.12.2023
Как оптимизировать код Дейкстры в PHP?
Я указываю этот вопрос для исходного кода PHP, где у меня есть исходный код для Дейкстры, написанный на PHP, когда я применяю этот алгоритм к Graph, состоящему из baout 7000 узлов, процесс становится чрезвычайно медленным и потребляет огромное...
2715 просмотров
c c++ php dijkstra
schedule 24.02.2024
Проблема алгоритма кратчайшего пути Дейкстры
Итак, я пытаюсь закодировать алгоритм кратчайшего пути Дейкстры на С++. По какой-то причине он не правильно суммирует расстояния... Вот что у меня есть для кода. Вы можете игнорировать раздел, в котором я копирую путь к стеку, потому что я знаю,...
1881 просмотров
c++ debugging dijkstra
schedule 07.04.2024
Реализация алгоритма Дейкстры с использованием минимальной кучи, но не удалась
Я пытаюсь реализовать Dijkstra's Algorithm с помощью минимальной кучи в java, но каждый раз получаю неправильный вывод. Здесь я нашел ту же тему на С++. Ниже мой график. Узел A, окрашенный в зеленый цвет, является источником, а узел F,...
6005 просмотров
java graph algorithm shortest-path dijkstra
schedule 16.03.2024
Модификация алгоритма Дейкстры
Я знаю алгоритм кратчайшего пути Дейкстры. Однако, если бы я изменил его так, чтобы вместо поиска кратчайшего пути он находил самый длинный путь с использованием жадного алгоритма. Что мне нужно сделать с кодом ниже: Вот что я использую: в...
582 просмотров
graph algorithm dijkstra graph-algorithm
schedule 20.01.2024
Реализация алгоритма Дейкстры дает неверные результаты
Мне нужна помощь в реализации алгоритма Дейкстры, и я надеялся, что кто-то сможет мне помочь. У меня это так, что он печатает некоторые маршруты, но не фиксирует правильную стоимость пути. Вот моя структура узла: class Node {...
1100 просмотров
c# algorithm dijkstra
schedule 05.06.2024
Создание случайного неориентированного графа в C++
Проблема в том, что мне нужно создать случайный неориентированный граф для тестирования эталонного теста алгоритма Дейкстры использование массива и кучи для хранения вершин. Насколько мне известно, реализация кучи должна быть быстрее, чем массив,...
4116 просмотров
c++ random graph dijkstra creation
schedule 16.03.2024
Дорожная карта с туннелями
Учитывая дорожную карту между несколькими городами, с дорогами между двумя городами, содержащими туннели, ваша цель состоит в том, чтобы найти кратчайшие возможные пути между начальным городом и всеми другими городами так, чтобы каждый путь содержал...
110 просмотров
c algorithm shortest-path dijkstra
schedule 24.10.2022
Полный граф только с двумя возможными затратами. Какова стоимость кратчайшего пути от 0 до N - 1
Вам дан полный неориентированный граф с N вершинами. Все ребра, кроме K, имеют стоимость A. Эти K ребер имеют стоимость B, и вы знаете их (как список пар). Какова минимальная стоимость от узла 0 до узла N - 1. 2 <= N <= 500k 0 <= K...
989 просмотров
graph algorithm shortest-path dijkstra breadth-first-search
schedule 04.04.2024
Набор кратчайших путей с несколькими начальными и множественными концами
У меня проблема с кратчайшим путем в ориентированном взвешенном графе. Я знаю Dijkstra , BFS , DFS . Однако у меня есть a set of vertices S для отправных точек и a set of vertices E to end . S и E не пересекаются. Итак, как я могу найти...
1978 просмотров
optimization algorithm computer-science shortest-path dijkstra
schedule 26.11.2023
Реализация кратчайшего пути из одного источника: приоритет по сравнению с очередью FIFO
В зависимости от специфики проблемы в контексте задачи о кратчайшем пути с одним источником обычно упоминаются два алгоритма: алгоритм Дейкстры и алгоритм Беллмана-Форда. Алгоритм Дейкстры работает с положительными весами ребер, тогда как алгоритм...
909 просмотров
queue shortest-path dijkstra bellman-ford priority-queue
schedule 01.05.2024
Время работы алгоритма Дейкстры - приоритетная очередь (куча)
Мне трудно понять, почему сложность алгоритма Дейкстры с кучей составляет O ((m + n) * log (n)), где m - количество ребер, а n - количество вершин. Насколько я понимаю: Теперь я знаю, что нужно удалить минуты. (Каждое удаление min берет log (n)...
970 просмотров
algorithm time-complexity dijkstra
schedule 11.12.2023
вычисление веса графика в Python с помощью NetworkX
Я использую networkx для вычисления кратчайшего расстояния (с точки зрения веса) между двумя вершинами в ориентированном взвешенном графе. Я думаю, что отношение алгоритм dijkstra_path_length является правильным для использования здесь, но я не...
1574 просмотров
python graph networkx dijkstra
schedule 31.10.2023
Список смежности Дейкстры
У меня возникла проблема с преобразованием псевдокода алгоритма Дейкстраса в реальный код. Мне был предоставлен список смежности, такой как «Местоположение - соседнее местоположение - расстояние до местоположения», пример для одного узла: AAA AAC 180...
1866 просмотров
java algorithm dijkstra adjacency-list
schedule 31.01.2024
Поиск кратчайшего пути с помощью Дейкстры с использованием кучи Фибоначчи?
Я реализовал C # Dijkstra с кучей Фибоначчи, используя SO вопрос и эту версию на Java , которая очень чистый, лаконичный и хорошо документированный. Я изменил DirectedGraph, чтобы сделать его неориентированным графом. Однако у меня есть 2...
434 просмотров
java c# shortest-path dijkstra
schedule 08.05.2024
Кратчайший путь в ориентированном взвешенном графе, который использует не более k вершин
Я пытаюсь решить проблему SSSP в связном ориентированном взвешенном циклическом графе с неотрицательными весами. Уловка здесь в том, что эта проблема запрашивает SSSP, который использует не более k вершин. Я попытался использовать модифицированный...
1290 просмотров
c++ graph algorithm shortest-path dijkstra
schedule 30.09.2022
Модифицированный алгоритм Дейкстры
Нам дан ориентированный граф с весами ребер W, лежащими между 0 и 1. Стоимость пути от исходного узла к целевому — это произведение весов ребер, лежащих на пути от исходного узла к целевому. Я хотел узнать об алгоритме, который может найти путь с...
3786 просмотров
graph algorithm shortest-path dijkstra heuristics
schedule 17.10.2022
Вызов кратчайшего пути
Как в графе с начальной вершиной S и конечной вершиной E найти k кратчайших путей из S в E при условии, что все вершины нужно посетить ровно один раз? Граф может иметь циклы. Может кто-нибудь уточнить, как использовать алгоритм Дейкстры или...
124 просмотров
graph dijkstra viterbi
schedule 03.04.2024
Как получить минимум определенных элементов массива с помощью Python?
Мне нужно знать минимальный элемент данных для определенных элементов в повторяющемся массиве. У меня есть три массива dist, Q и вершина: dist = [ 0. inf inf inf inf] vertex = [2 4 5 7 8] Q = [2 4 5 7 8] Массив dist — это значения...
69 просмотров
python-3.x python numpy dijkstra
schedule 07.03.2024
Как получить вес наименьшего пути между двумя узлами?
У меня есть граф networkx на Python со взвешенными ребрами. Я хочу получить вес наименьшего пути между двумя узлами. В настоящее время я получаю узлы кратчайшего пути из реализации nx.shortest_path, а затем перебираю каждую пару и суммирую веса...
1311 просмотров
python-3.x python shortest-path networkx dijkstra
schedule 29.03.2024