Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
#1

Вывод пути (алгоритм Дейкстры) - C++

04.06.2014, 01:58. Просмотров 3120. Ответов 31
Метки нет (Все метки)

Реализация алгоритма Дейкстра.
В массиве distance - найденные кратчайшие пути, visited - логический, для хранения информации о посещенных вершинах.
Вместо "нубского" вывода пройденного пути из первой вершины в последнюю, необходимо реализовать нормальный вывод точек, через которые был проложен путь.
C++
1
cout << "А(" << distance [u-8] << ")" << " -> " << " Б(" << distance [u-7] << ")" << " -> " << " E(" << distance[5] << ")" << " -> " << " Ж(" << distance[6] << ")" << " -> " << " З(" << distance[u-1] << ")" << " -> " << " K(" << distance[u] << ")" << endl;
Кликните здесь для просмотра всего текста
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
const int V=10;
 
void Dejkstra(int GR[V][V], int st)
{
    int max=100;
    int distance[V], count, index, i, u, m=st+1;
    bool visited[V];
 
    for (i=0; i<V; i++)
    {
        distance[i]=max;
        visited[i]=false;
    }
 
    distance[st]=0;
 
    for (count=0; count<V-1; count++)
 
        {
            int min=max;
            for (i=0; i<V; i++)
                if (!visited[i] && distance[i]<=min)
                    {
                        min=distance[i]; index=i;
                    }
 
 
    u=index;
    visited[u]=true;
 
    for (i=0; i<V; i++)
 
        if (!visited[i] && GR[u][i] && distance[u]!=max &&
            distance[u]+GR[u][i]<distance[i])
            distance[i]=distance[u]+GR[u][i];
        }
        cout<<"Длина пути Винни до пятака:\n";
 
        //for (i=0; i<V; i++)
            if (distance[i]!=max)
           // cout<<m<<" > "<<i+1<<" = "<<distance[i]<< " Пройденные точки: "   << endl;
 
            cout<<m<<" > "<<V<<" = "<<distance[u] << endl << endl;
 
       // else  cout<<m<<" > "<<i+1<<" = "<<"маршрут недоступен"<<endl << endl;
 
 
       // if (m==1)
 
            cout << endl;
            cout << "Путь из точки А к точке К: " << endl;
            cout << "А(" << distance [u-8] << ")" << " -> " << " Б(" << distance [u-7] << ")" << " -> " << " E(" << distance[5] << ")" << " -> " << " Ж(" << distance[6] << ")" << " -> " << " З(" << distance[u-1] << ")" << " -> " << " K(" << distance[u] << ")" << endl;
 
 
            cout << endl << "Медведю пилить до хрю-хрю аж " << distance[i-1]  << " чего-то там!";
 
        if (distance[i-1] > 40 )
        {   Sleep (4000);
            cout << endl << endl << "Может, домой вернуться? :(" << endl << endl; Sleep (2000);
            cout << "Кажется, дождь начинается... :(" << endl;Sleep(1500);}
}
 
 
int main()
 
{
    setlocale(LC_ALL, "Rus");
 
    int start, GR[V][V]=
    {
        {0, 20, 25, 30, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 5, 0, 10, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 10, 15, 0, 0, 0},
        {0, 0, 0, 0, 25, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 15, 0, 5, 10, 20},
        {0, 0, 0, 0, 0, 0, 10, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 15, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    };
 
 
        cout<<"Начальная вершина >> ";
 
        start = 1;
 
       /* if ((start > 10)||(start < 1))
        {
            cout<<"Шот не то..." << endl;
            Sleep (3000);
            cout << "Думаю..." << endl;
            Sleep (3000);
 
            cout << "Ищем ошибку..." << endl << endl;
            Sleep (3000);
            cout << "Неверный ввод!" << endl;
            Sleep(3000);
            cout << "Аварийное завершение работы..." << endl;
            Sleep (3000);
            system("cls");
            cout<<"Давай, до свидания!";
 
            return 0;
        }
*/
        Dejkstra(GR, start-1);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.06.2014, 01:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вывод пути (алгоритм Дейкстры) (C++):

Определение кратчайшего пути алгоритмом Дейкстры - C++
Разработка программного комплекса для определения кратчайшего пути алгоритмом Дэйстри. Программный комплекс решает задачу поиска самого...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Определение радиуса и соответствующего радиусу пути взвешенного орграфа на основе алгоритма Дейкстры - C++
Реализация АТД « Взвешенный орграф». Граф представлен в виде списков смежности. Определение радиуса и соответствующего радиусу пути...

Алгоритм Дейкстры - C++
Как на С++ в консольном приложении описать алгоритм Дейкстры?

Алгоритм Дейкстры - C++
Всем добрый день,уважаемые программисты! Помогите пожалуйста решить вот эту задачу алгоритмом дейкстры. Вроде сам алгоритм правильно...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
05.06.2014, 00:45  [ТС] #16
мне же нужен путь из 1 точки в 10, поэтому:
C++
1
start = 1, finish = 10
iliya785
23 / 23 / 8
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 00:53 #17
матрица g[n][n], где n = 10, это значит что можно работать со столбцами и строками размера <= 9 (нумерация с 0). Происходит выход за пределы массива.

Добавлено через 5 минут
а vector в C++ , штука полезная. Вообще это динамический массив.
объявляется он так vector < type (например int) > название.
у него есть несколько конструкторов например:
vector <type> name(size,val) - выделяем массив name на size элеметов и заполняем его val
vector <type> name(size) - выделяем массив name на size элеметов и заполняем дефолтными значениями
vector <type> name - это динамический массив, добавление с помощью метода push_back
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
05.06.2014, 00:56  [ТС] #18
понял
C++
1
int start = 0, finish = 9
выводит неправильный путь:
0-2-6-7-9
а должен быть
0-1-5-6-7-9
iliya785
23 / 23 / 8
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 00:59 #19
нашёл баг , теперь всё ок

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int n = 10;
const int inf = 1000*1000*1000;
 
int start, g[n][n]=
    {
        {0, 20, 25, 30, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 3, 0, 10, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 10, 15, 0, 0, 0},
        {0, 0, 0, 0, 25, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 15, 0, 5, 10, 20},
        {0, 0, 0, 0, 0, 0, 10, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 15, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    };
 
int main()
{
    vector <int> d(n+5,inf),p(n+5,-1);
    vector <bool> used(n+5);
    int start = 2, finish = 3,mn,u;
    d[start] = 0;
    for (int i=0;i<n;++i){
        mn = inf, u = -1;
        for (int j=0;j<n;++j)
            if (!used[j] && d[j] < mn)
                mn = d[j], u = j;
        if (u == -1)    break;
        used[u] = true;
        for (int j=0;j<n;++j)
            if (d[j] > d[u] + g[u][j] && g[u][j] > 0)
                d[j] = d[u] + g[u][j], p[j] = u;
    }
    vector <int> v;
    if (p[finish] == -1)
        cout<<"No way\n";
    else{
        for (int u = finish ; u != -1; u = p[u])
            v.push_back(u);
        reverse(v.begin(),v.end());
        for (int i=0;i<v.size();++i){
            if (i > 0)    cout<<"->";
            cout<<v[i];
        }
    }
}
Добавлено через 1 минуту
0 - это отсутствие ребра , или налчие ребра нулевой стоимости ?
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
05.06.2014, 01:03  [ТС] #20
то есть по этому пути вес получится 65, а минимальный - 60

Добавлено через 2 минуты
0 - отсутствие ребра

Добавлено через 2 минуты
теперь выводит другой путь - 0-1-3-4-7-9, но вес всё равно 65, а не нужный 60
iliya785
23 / 23 / 8
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 01:19 #21
ответ абсолютно верный - и там и там вес 65(вес кратчайшего пути и там и там я проверил ) Кратчайший путь в звешенном графе определяется суммой всех рёбер входящих в этот путь, просто в этом графе несколькократчайших путей.

Добавлено через 3 минуты
для проверки я менял матрицу , поэтому в разных вариантах разные матрицы , используй послелний вариант

Добавлено через 48 секунд
перепроверь матрицу

Добавлено через 1 минуту
а какой должен быть для 60 напиши плс

Добавлено через 5 минут
Скажи какой путь кратчайший путь. Перепроверь матричку(я её менял и не один раз).
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
05.06.2014, 01:20  [ТС] #22
для 60 кратчайший путь 0-1-5-4-7-9
0-20-30-45-50-60

Добавлено через 54 секунды
Матрицу перепроверил
iliya785
23 / 23 / 8
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 01:29 #23
g[5][4] = 0 (отсутствие ребра), значит такого пути нет
ты задал не существующий путь

Добавлено через 5 минут
теперь всё так?
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
05.06.2014, 01:32  [ТС] #24
Вывод пути (алгоритм Дейкстры)
А какое значение нужно поставить туда?
На графе такой путь есть
А-Б-Е-Д-З-К

до меня дошло))
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
05.06.2014, 01:36  [ТС] #25
C++
1
        g[5][4]=15;
Добавлено через 48 секунд
а как вывести длину пути?
какой массив отвечает за это?

Добавлено через 1 минуту
ну или чтобы больше не было вопросов, закомментируйте код, пожалуйста. Если я ,конечно, не совсем ещё достал Вас)
iliya785
23 / 23 / 8
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 01:45 #26
Сообщение было отмечено автором темы, экспертом или модератором как ответ
в матрице ошибка теперь работает
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int n = 10;
const int inf = 1000*1000*1000;
 
int start, g[n][n]=
     {
        {0, 20, 25, 30, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 5, 0, 10, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 10, 15, 0, 0, 0},
        {0, 0, 0, 0, 25, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 15, 0, 5, 10, 20},
        {0, 0, 0, 0, 15, 0, 10, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 15, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    };
 
int main()
{
    vector <int> d(n+5,inf),p(n+5,-1);
    vector <bool> used(n+5);
    int start = 0, finish = 9,mn,u;
    d[start] = 0;
    for (int i=0;i<n;++i){
        mn = inf, u = -1;
        for (int j=0;j<n;++j)
            if (!used[j] && d[j] < mn)
                mn = d[j], u = j;
        if (u == -1)    break;
        used[u] = true;
        for (int j=0;j<n;++j)
            if (d[j] > d[u] + g[u][j] && g[u][j] > 0 )
                d[j] = d[u] + g[u][j], p[j] = u;
    }
    vector <int> v;
    if (p[finish] == -1)
        cout<<"No way\n";
    else{
        for (int u = finish ; u != -1; u = p[u])
            v.push_back(u);
        reverse(v.begin(),v.end());
        for (int i=0;i<v.size();++i){
            if (i > 0)    cout<<"->";
            cout<<v[i];
        }
    }
    cout<<"\n"<<d[finish]<<"\n";
}
Добавлено через 1 минуту
также нужно было указать ориентированный граф или нет

Добавлено через 30 секунд
теперб уж точно всё? :-)
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
05.06.2014, 01:48  [ТС] #27
почти)))
последний рывок)
как примерно это всё работает?


C++
1
const int inf = 1000*1000*1000;
C++
1
2
    vector <int> d(n+5,inf),p(n+5,-1);
    vector <bool> used(n+5);
C++
1
2
3
4
5
6
7
8
9
10
for (int i=0;i<n;++i){
        mn = inf, u = -1;
        for (int j=0;j<n;++j)
            if (!used[j] && d[j] < mn)
                mn = d[j], u = j;
        if (u == -1)    break;
        used[u] = true;
        for (int j=0;j<n;++j)
            if (d[j] > d[u] + g[u][j] && g[u][j] > 0 )
                d[j] = d[u] + g[u][j], p[j] = u;
C++
1
2
3
4
5
6
7
8
9
if (p[finish] == -1)
        cout<<"No way\n";
    else{
        for (int u = finish ; u != -1; u = p[u])
            v.push_back(u);
        reverse(v.begin(),v.end());
        for (int i=0;i<v.size();++i){
            if (i > 0)    cout<<"->";
            cout<<v[i];
iliya785
23 / 23 / 8
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 01:52 #28
d - массив расстояний , p - предков , used - посещений, g[][] - матрица смежности.
P.S. На вы можно и не обращаться сам студент , только недавно подобное сдавал, если нужны реализации других алгоритмов по этой дисциплине могу скинуть :-)

Добавлено через 2 минуты
1 объявление большой константы (типа бесконечность)
2 объявление массивов (выше описно какие именно)
3 Алгоритм Дейкстры
4 Восстановление пути
Aecttann
6 / 6 / 0
Регистрация: 19.10.2013
Сообщений: 334
05.06.2014, 01:57  [ТС] #29
спасибо

Не по теме:

дискретка она такая)))
кидай всё, что есть)))
сейчас в лс мыло кину



Добавлено через 3 минуты
iliya785,

Не по теме:

или не скину мыло...
iliya785 has chosen not to receive private messages or may not be allowed to receive private messages.

iliya785
23 / 23 / 8
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 02:00 #30
а лучше я их кину сюда
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2014, 02:00
Привет! Вот еще темы с ответами:

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

Алгоритм Дейкстры - C++
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет. #include&lt;iostream&gt; #include&lt;fstream&gt; ...

Алгоритм Дейкстры - C++
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на паскале, а именно вот этого кода const int INF = 1000000000; ...

Алгоритм Дейкстры - C++
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.06.2014, 02:00
Ответ Создать тему
Опции темы

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