Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
#1

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

04.06.2014, 01:58. Просмотров 4296. Ответов 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);
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.06.2014, 01:58
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Вывод пути (алгоритм Дейкстры) (C++):

Алгоритм Дейкстры, нахождение кратчайшего пути
Доброго времени суток всем! У меня вопрос. Написала программку для нахождения...

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using...

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

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

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

31
iliya785
23 / 23 / 12
Регистрация: 04.06.2014
Сообщений: 80
04.06.2014, 02:36 #2
http://e-maxx.ru/algo/dijkstra , прочитай пункт восстановление пути
0
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
04.06.2014, 03:03  [ТС] #3
iliya785, читал, читаю - ничего не выходит
0
iliya785
23 / 23 / 12
Регистрация: 04.06.2014
Сообщений: 80
04.06.2014, 22:22 #4
если всё так плохо , то могу допилить , а также подебажить код. Также могу объяснить восстановление пути или сам алгоритм.
0
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
04.06.2014, 22:35  [ТС] #5
да сам алгоритм и код я понимаю, мне нужны идеи насчёт того, как построить путь
0
iliya785
23 / 23 / 12
Регистрация: 04.06.2014
Сообщений: 80
04.06.2014, 23:03 #6
Лучший ответ Сообщение было отмечено Aecttann как решение

Решение

заведём массив p, где p[i] - вершина из которой мы пришли в вершину i(предок i), изменять значения этого массива будем там же где и улучшаем массив расстояний(у тебя это массив distance, в теле if'a, который на строке 40 нужно дописать p[i] = u). Теперь как восстанавливаем путь: пусть мы находимся в вершине finish(путь из start->finish) теперь перейдём в предка вершины finish(это p[finish]), далее перейдём в предка вершины p[finish](p[p[finish]]) и продолжаем пока не прийдем к старт(если надо могу эту часть кода написать). Остаётся только перевернуть путь (т.к. мы двигались из finish->start). Если есть ещё вопросы пиши, постараюсь ответить
0
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
04.06.2014, 23:23  [ТС] #7
iliya785,
Цитата Сообщение от iliya785 Посмотреть сообщение
если надо могу эту часть кода написать
не понимаю, что и как сделать в этом цикле)
C++
1
2
3
4
5
6
7
8
9
10
11
12
int p[10];
 
 
    for (i=0; i<V; i++)
 
        if (p[i] = u
            
        
            !visited[i] && GR[u][i] && distance[u]!=max &&
            distance[u]+GR[u][i]<distance[i])
            distance[i]=distance[u]+GR[u][i];
        }
0
iliya785
23 / 23 / 12
Регистрация: 04.06.2014
Сообщений: 80
04.06.2014, 23:25 #8
C++
1
2
3
4
5
6
7
    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];
                  p[i] = u;
           }
также по дефолту заполнить массив p, значениям -1
0
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
04.06.2014, 23:39  [ТС] #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int p[10];
p[0]= -1;
p[1]= -1;
p[2]= -1;
p[3]= -1;
p[4]= -1;
p[5]= -1;
p[6]= -1;
p[7]= -1;
p[8]= -1;
p[9]= -1;
    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];
                  p[i] = u;
           }
 
cout << p[i];
0
Миниатюры
Вывод пути (алгоритм Дейкстры)  
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
04.06.2014, 23:46  [ТС] #10
и так по циклу с моей первой точки, до последней, выводится длина пути
0
iliya785
23 / 23 / 12
Регистрация: 04.06.2014
Сообщений: 80
04.06.2014, 23:49 #11
скинь весь код
0
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
04.06.2014, 23:52  [ТС] #12
Кликните здесь для просмотра всего текста
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
#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;
 
int p[10];
p[0]= -1;
p[1]= -1;
p[2]= -1;
p[3]= -1;
p[4]= -1;
p[5]= -1;
p[6]= -1;
p[7]= -1;
p[8]= -1;
p[9]= -1;
    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];
                  p[i] = u;
           }
 
cout << p[i];
 
 
        cout<<"Длина пути Винни до пятака:\n";
 
        //for (i=0; i<V; i++)
            if (distance[i]!=max)
 
 
            cout<<m<<" > "<<V<<" = "<<distance[u] << endl << endl;
            
cout << "Путь из точки А к точке K: " << endl;
 
        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},
    };
        start = 1;
 
        Dejkstra(GR, start-1);
}
0
iliya785
23 / 23 / 12
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 00:37 #13
Написпл весь код снуля (были серьёзные баги) statrt , finish можешь изменить из main
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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
 
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, 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,inf),p(n,-1);
    vector <bool> used(n);
    int start = 0, 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;
        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];
        }
    }
}
Добавлено через 5 минут
напиши , что нужно добавить , я тогда сделаю , а то чувствую затянится это надолго
1
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
05.06.2014, 00:40  [ТС] #14
ну и ну
теперь бы понять что это вообще всё такое, для чего нужны вектора (не знаком с ними))))
и ещё когда меняю значения старт и финиш, оно зацикливается и завершается

также нужно вывести вес пути
он должен быть 60
0
iliya785
23 / 23 / 12
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 00:42 #15
напиши на каких данных циклится
0
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
05.06.2014, 00:45  [ТС] #16
мне же нужен путь из 1 точки в 10, поэтому:
C++
1
start = 1, finish = 10
0
iliya785
23 / 23 / 12
Регистрация: 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
1
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
05.06.2014, 00:56  [ТС] #18
понял
C++
1
int start = 0, finish = 9
выводит неправильный путь:
0-2-6-7-9
а должен быть
0-1-5-6-7-9
0
iliya785
23 / 23 / 12
Регистрация: 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 - это отсутствие ребра , или налчие ребра нулевой стоимости ?
1
Aecttann
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 342
05.06.2014, 01:03  [ТС] #20
то есть по этому пути вес получится 65, а минимальный - 60

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

Добавлено через 2 минуты
теперь выводит другой путь - 0-1-3-4-7-9, но вес всё равно 65, а не нужный 60
0
05.06.2014, 01:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2014, 01:03
Привет! Вот еще темы с решениями:

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

Алгоритм Дейкстры
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на...

Алгоритм Дейкстры
Здравствуйте!!! Есть код для нахождения длин от начальной вершины до всех...

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


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

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

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