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

Алгоритм Дейкстра. Поиск кратчайшего пути с запоминанием маршрута

23.04.2016, 09:32. Показов 2818. Ответов 5
Метки нет (Все метки)

Всем привет, есть алгоритм Дейкстра, который находит минимальный маршрут из главной вершины во все остальные. Как сделать, чтобы помимо этого он запоминал маршрут по которому идет? Т.е. из Х1 - Х3 - Х5 (путь от главной вершины до пятой)

C++
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
void Graph::Dijkstra() {
    int index;
 
    int *distance = new int[size];
    int *visited = new int[size];
 
    int ** info = new int *[size];
    for (int i = 0; i < size; i++) {
        info[i] = new int[size];
    }
 
 
    for (int i = 0; i < size; i++) {
        distance[i] = INT_MAX;
        visited[i] = 0;
    }
 
    distance[Capital-1] = 0;
 
    for (int count = 0; count < size - 1; count++){
        int min = INT_MAX;
 
        for (int i = 0; i < size; i++) {
            if (!visited[i] && distance[i] <= min) {
                min = distance[i]; index = i;
            }
        }
 
        visited[index] = 1;
        for (int i = 0; i < size; i++) {
            if (!visited[i] && Matrix[index][i] && distance[index] != INT_MAX && distance[index] + Matrix[index][i] < distance[i]) {
                distance[i] = distance[index] + Matrix[index][i];
            }
        }
    }
}
В Matrix хранится граф:

C++
1
2
3
4
5
6
7
8
9
10
9
1 20 40 0 55 81 0 25 15
20 1 10 0 0 0 0 0 35
40 10 1 5 0 0 15 0 0
0 0 5 1 55 0 0 80 0
55 0 0 55 1 5 0 0 0
81 0 0 0 5 1 25 8 0
0 0 15 0 0 25 1 5 0
25 0 0 80 0 8 5 1 12
15 35 0 0 0 0 0 12 1
Двумерный массив info я создал для хранения в нем как раз таки пути, но вот как его записать - не знаю

Добавлено через 13 часов 40 минут
ап .
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.04.2016, 09:32
Ответы с готовыми решениями:

Поиск пути (алгоритм А* / Дейкстра)
Пытался реализовать алгоритм A* (точнее пока алгоритм Дейкстры т.е. без эвристики) по этой статье:...

Поиск кратчайшего пути (алгоритм Уоршала)
В области имеется N городов, соединены автобусными маршрутами. Стоимость билета с i-го города в j-й...

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

Алгоритм Флойда (графы - поиск кратчайшего пути)
Собственно очень нужен алгоритм на VBA. Народ если кто то видел, или у кого то есть, поделитесь...

5
1225 / 745 / 167
Регистрация: 05.12.2015
Сообщений: 2,210
23.04.2016, 12:45 2
Цитата Сообщение от anonfor1 Посмотреть сообщение
алгоритм Дейкстра
Алгоритм Дейкстры. Он был Дейкстра, а не Дейкстр.

Цитата Сообщение от anonfor1 Посмотреть сообщение
но вот как его записать - не знаю
В момент, кодга следующая вершина выбрана - путь до нее уже не изменится. Копируем путь до предыдущей вершины и добавляем в него выбранную. (Хотя путь потом можно восстановить по весу ребер и меткам вершин).
0
0 / 0 / 0
Регистрация: 22.04.2016
Сообщений: 3
23.04.2016, 22:03  [ТС] 3
Цитата Сообщение от avgoor Посмотреть сообщение
Копируем путь до предыдущей вершины и добавляем в него выбранную.
Как его запоминать в данном алгоритме?
0
1225 / 745 / 167
Регистрация: 05.12.2015
Сообщений: 2,210
24.04.2016, 00:23 4
Цитата Сообщение от anonfor1 Посмотреть сообщение
Как его запоминать в данном алгоритме?
Что конкретно не понятно?
0
Модератор
1623 / 1078 / 485
Регистрация: 17.07.2012
Сообщений: 5,308
24.04.2016, 01:54 5
Восстановление путей
0
0 / 0 / 0
Регистрация: 22.04.2016
Сообщений: 3
24.04.2016, 13:02  [ТС] 6
Переделал под алгоритм Флойда:
C++
1
2
3
4
5
6
7
8
9
10
void Graph::Floyd() {
    for (int k = 0; k < size; ++k)
        for (int i = 0; i < size; ++i)
            for (int j = 0; j < size; ++j) {
                if (Matrix[i][k] + Matrix[k][j] < Matrix[i][j]) {
                    Matrix[i][j] = Matrix[i][k] + Matrix[k][j];
                    Predok[i][j] = k;
                }
            }
}
Как правильно сохранять матрицу предков? Сохраняя так, как делаю я - получаю неверную матрицу. И как в дальнейшем восстанавливать путь?

Добавлено через 1 час 28 минут
Спасибо, решил задачу сам
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.04.2016, 13:02

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Поиск кратчайшего пути (алгоритм Дейкстры) с наименьшим максимальным ребром
Есть классическая реализация Дейкстры, пытаюсь добавить условие: если есть несколько кратчайших...

Алгоритм поиска кратчайшего маршрута
Моё почтение всем! Буду ОЧЕНЬ благодарен тому, кто сможет мне помочь найти алгоритм (или исходник...

Поиск кратчайшего маршрута
Помогите, пожалуйста, реализовать алгоритм поиска кратчайшего маршрута методом Форда-Беллмана и...

Алгоритм решения задачи по определению кратчайшего маршрута
Как определить кратчайший маршрут, проходящий через все населенные пункты? &quot;В лоб&quot; не хочется, а...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.