Алгоритм дейкстры в excel

Обновлено: 07.01.2025

исходные данные даны матрицей :

1 5 6 9 10 20 21 22 33
2 3 4 11 12 * * * *
3 1 5 19 20 25 * * *
******************
40 26 27 29 31 37 * * *

надо чтобы прокладывало маршрут(односторонний) из начальной точки(например 1) в конечную(например18) и его выводило (например 1-5-20-13-18), у каждой точки есть от 0 до 10 точек в которые можно из нее попасть но в одну сторону( из этих точек обратно нельзя) и условие что в цепочке не меньше 3х точек и не больше 5

я так понял надо применить Алгоритм Дейкстры для поиска кратчайшего пути в графе:
for k:=1 to N do
for i:=1 to N do
for j:=1 to N do
d[i,j]:=min(d[i,j], d[i,k]+d[k,j]);

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

тут помогают или нет?)
из точки 1 можно попасть в 5 ,6 9, 10,20,21,22,23
из 2 в 3,4,11 или 12 соответственно, и так далее это пояснение к исходникам

уверен что задачка примитивна и решается на раз два помогите пожалуйста)

Последний раз редактировалось Эдгар; 20.10.2008 в 22:49 . 41001804815208 - ЮMoney бывш.Яндекс-кошелек благодарности за удачные советы и решения можно отправлять прямо сюда)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете

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

Итак, в моей задаче в качестве исходных взято 100 точек. В нижней таблице случайным образом написано из какой точки в какую есть путь. Предполагается, что из точки с меньшим порядковым номером можно попасть только в точку с большим номером. Количество тропинок из каждой точки равно 5 (можно до 10, нарисована сетка). Если в Вашей задаче число тропинок произвольное, необходимо написать реальные пути, а у тех точек, а где их мало - дополнить "фиктивными путями" до точки 100, которой нет на плане.

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

Задача решена алгоритмом Гончаренко. Данный алгоритм заключается в довольно примитивном переборе всех возможных вариантов.

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

Решение Дейкстрой и Левитом находятся в одном файле, т.к. исходные данные (описание графа) одинаковое, и подход к решению очень похожий
Граф в решении Форда-Беллмана хранит не матрицу смежности вершин, а описание ребер графа.

Сделал еще одну реализацию - алгоритм Дейкстры для разреженного графа
Протестировал на реальных данных, данные взял здесь (New York City)
Количество точек - 264346
Количество ребер - 733846

Стандартный алгоритм Дейкстры "вешается", не дождался расчтов, оно и понятно асимптотика алгоритма O(n 2 + m)

Дейкстра для разрежнного графа на реальных данных показала себя достаточно хорошо, время расчетов в пределах нескольких секунд.
Больше всего понравился алгоритм Левита, в виду простой реализации, а также из-за достаточно хорошей скорости.
При этом нужно отметить, что алгоритмом Левита находит минимальное расстояние от текущей точки до всех остальных.
В алгориме Дйкстры можно ограничить поиск, как только найден путь к необходимой точке, это позволяет ускорить Дейкстру.
Если не ограничивать поиск, а искать все пути, то алгортм Декстры в разы медленнее алгоритма Левита.

Файл находится здесь (внимание, размер 10 МБ)

ЗЫ: В данной рализации изменил формат хранния графа на листе, не в виде матрицы смежности, а описанием ребер: окуда, куда, расстояние
ЗЗЫ: У кого-нибуть есть реальные данные по описанию расстояний по карте России? хотелось бы потестировать

Стандартный алгоритм Дейкстры "вешается", не дождался расчтов, оно и понятно асимптотика алгоритма O(n 2 + m)

Файл находится здесь (внимание, размер 10 МБ)

Стандартный алгоритм Дейкстры "вешается", не дождался расчтов, оно и понятно асимптотика алгоритма O(n 2 + m)

Файл находится здесь (внимание, размер 10 МБ)

Алгоритм Дейкстры
Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до.

Алгоритм Дейкстры С++
Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление графа – матрица.

Алгоритм Дейкстры
Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности, и все возможные.

Алгоритм Дейкстры
Что-то у меня Дейкстра не работает. прошу помощи у вас. Сам уже часа 1.5 сижу и не могу найти.

двумерный массив A[x][y] в котором записаны расстояния, между вершинами x и y графа Это же матрица смежности твоего графа?
Сначала можно посмотреть темы снизу или просто загуглить, все это давно есть Я в этом не мастер-фломастер, но попробую - вот мой вариант реализации, если гуглить лень

Спасибо огромное! Вы мне очень помогли

Добавлено через 1 час 16 минут

Я в этом не мастер-фломастер, но попробую - вот мой вариант реализации, если гуглить лень А можно еще вопросик, как мне найти сам путь? По вершинам. То есть нужно найти кратчайший путь от 1 до 5, и нужно чтобы вывело например 135 А можно еще вопросик, как мне найти сам путь? По вершинам. То есть нужно найти кратчайший путь от 1 до 5, и нужно чтобы вывело например 135

Либо хранить. Вверху есть строчку p[j] = p[j]+что-то там
Заводите еще один vector<int> parent(n, -1);
И после этой строки вставляете parent[j] = i;

Вывод тогда будет таким

Либо искать. Давайте представим, что граф неориентированный. Тогда это будет примерно так
cout << pos << " ";
while(pos != №вершины от которой ищем) for(int i = 0; i < n; i++)
if (p[pos]==p[i]+matrix[pos][i]) cout << i << " ";
pos = i;
break;
>
>

а что здесь за массив p?

Добавлено через 22 часа 29 минут
Вот что у меня получилось. ищет короткие пути из любой вершины в любую, но вот как сам путь найти я, хоть убейте, не допру

Решение

Leonsmoke, цитата с интернета : разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из s до любой вершины. Для этого достаточно так называемого массива предков: массива p[], в котором для каждой вершины v != s хранится номер вершины p[v], являющейся предпоследней в кратчайшем пути до вершины v. Здесь используется тот факт, что если мы возьмём кратчайший путь до какой-то вершины v, а затем удалим из этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной p[v], и этот путь будет кратчайшим для вершины p[v]. Итак, если мы будем обладать этим массивом предков, то кратчайший путь можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в стартовую вершину s — так мы получим искомый кратчайший путь, но записанный в обратном порядке.

Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины v происходит улучшение расстояния до некоторой вершины to, мы записываем, что предком вершины to является вершина v:

Я хотел реализовать Алгоритм Дейкстры в надстройке Excel VBA и построил его используется следующим образом:

Define a list of paths with distances between points. This list needs to contain 3 headings that are used as flags to pick up where the list is. The 3 headings are !dijk:dat:from , !dijk:dat:to and !dijk:dat:dist
Specify from which point to which point you want to go. This is indicated with flags to the left of the cell. The flags are !dijk:get:from and !dijk:get:to
If the list of paths is on a different sheet, specify which sheet it is on by putting the name of the sheet in a cell next to a cell with the text !dijk:dat
Specify where the output should go. This is defined with a flag at the top left of where it should go. The flag is !dijk:steps
Push a button in the Ribbon that triggers Sub sCalcDijkstra() in a module in my Add-In

Пример фиктивного листа, который я использовал для тестирования:

Это процедура, которая выполняет всю работу:

Код работает, но мне хотелось бы получить некоторые отзывы по следующим аспектам:

Как я могу сделать это проще и интуитивно понятным для пользователя? Я знаю, что я могу использовать именованные диапазоны вместо флагов, но я бы предпочел сохранить его более очевидным, что использует код
Как я могу применить принцип DRY больше здесь. Я повторяю одни и те же шаблоны все время, но мне кажется, что детали слишком сильно меняют, чтобы просто вставить что-то вроде вложенных циклов в функцию.
Я использую Scripting.Dictionary для почти всего, что связано с его гибкостью и просто из-за того, что мне нравится, как это работает, но я подозреваю, что могут быть лучшие структуры данных, которые я могу использовать которые работают лучше для этого случая использования
В основе этого лежит цикл Do While True , который, вероятно, является ужасно неэффективным способом реализации алгоритма Дейкстры. Как я могу сделать его более эффективным?
Любая помощь/критика приветствуются. Я научил себя VBA с помощью Google, и я, возможно, делаю некоторые плохие вещи, которые я даже не понял.

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

Первая из этих «условностей» заключается в объявлении каждой переменной в верхней части блока, к которому они привязаны. Это реликвия «древних дней», где важно было знать, что было в процедуре и как вы могли обращаться к ним. Посмотрите, что это делает с читабельностью вашего кода на экране, который не находится в портретной ориентации:

Это . не очень полезно, потому что я не могу даже отдаленно сказать, какая переменная нужна там, где и даже нужна ли она .

Declare variables as close as possible to their usage.
This has the added benefit of reducing the mental strain when reading the code. You don't need to remember every variable declaration, only those in close proximity to understand the code.

Пока мы в этом разделе: я заметил, что вы префикс каждой из этих переменных с помощью v , скорее всего, для «Variable». Не делай этого. Это не добавляет никакой полезной информации к названию переменной и, откровенно говоря, не нужно.

Давайте перепишем это немного. Для одного комментарий является ложью, это не проверяет, что рабочая книга открыта, она проверяет, что свойство ActiveSheet глобального объекта приложения не является ничем. Кроме того, вы делаете это несколько сложнее для чтения, заставляя себя в однострочные if-statements:

Выполнение всей работы длительное и утомительное. Этот код может значительно выиграть от извлечения подпрограмм в фактические подпрограммы или Функции. Рассмотрим инкапсулирующие блоки кода, которые имеют пояснительный комментарий в свою собственную функцию:

Эта «перемагниченность» имеет явное преимущество, позволяя нам абстрагировать утомительные отдельные шаги на методы и объекты. Нам не нужно разбираться в разных силах 10 , чтобы понять, что делает этот суб.

Обратите внимание, что это также оборачивает использование GoTo, которое . проблематично в некоторых контекстах.

В заключение я хочу явно назвать материал, который я заметил как выдающийся:

Вы всегда получаете доступ к значению ячейки явно через Value : +1:
Вы используете словарь для отслеживания стоимости для данного узла.
Вы восстанавливаете обработку ошибок после On Error Resume Next и, похоже, пытались удержать области OERN как можно меньше
Вы подтверждаете свой ввод и имеете довольно чистый способ получить его со своего листа.

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

Читайте также: