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

@Aecttann · Регистрация: 19.10.2013

Студворк — интернет-сервис помощи студентам

Реализация алгоритма Дейкстра.
В массиве 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);
}

@iliya785 · 05.06.2014, 01:19

ответ абсолютно верный - и там и там вес 65(вес кратчайшего пути и там и там я проверил

) Кратчайший путь в звешенном графе определяется суммой всех рёбер входящих в этот путь, просто в этом графе несколькократчайших путей.

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

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

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

Добавлено через 5 минут
Скажи какой путь кратчайший путь. Перепроверь матричку(я её менял и не один раз).

@Aecttann · 05.06.2014, 01:20 **[ТС]**

для 60 кратчайший путь 0-1-5-4-7-9
0-20-30-45-50-60

Добавлено через 54 секунды
Матрицу перепроверил

@iliya785 · 05.06.2014, 01:29

g[5][4] = 0 (отсутствие ребра), значит такого пути нет
ты задал не существующий путь

Добавлено через 5 минут
теперь всё так?

@Aecttann · 05.06.2014, 01:32 **[ТС]**

А какое значение нужно поставить туда?
На графе такой путь есть
А-Б-Е-Д-З-К

до меня дошло))

@Aecttann · 05.06.2014, 01:36 **[ТС]**

C++
1
        g[5][4]=15;

Добавлено через 48 секунд
а как вывести длину пути?
какой массив отвечает за это?

Добавлено через 1 минуту
ну или чтобы больше не было вопросов, закомментируйте код, пожалуйста. Если я ,конечно, не совсем ещё достал Вас)

@iliya785 · 05.06.2014, 01:45

в матрице ошибка теперь работает

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 · 05.06.2014, 01:48 **[ТС]**

почти)))
последний рывок)
как примерно это всё работает?

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 · 05.06.2014, 01:52

d - массив расстояний , p - предков , used - посещений, g[][] - матрица смежности.
P.S. На вы можно и не обращаться сам студент , только недавно подобное сдавал, если нужны реализации других алгоритмов по этой дисциплине могу скинуть :-)

Добавлено через 2 минуты
1 объявление большой константы (типа бесконечность)
2 объявление массивов (выше описно какие именно)
3 Алгоритм Дейкстры
4 Восстановление пути

@Aecttann · 05.06.2014, 01:57 **[ТС]**

спасибо

Не по теме:

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

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

Не по теме:

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

@iliya785 · 05.06.2014, 02:00

а лучше я их кину сюда

@Aecttann · 05.06.2014, 02:02 **[ТС]**

Сообщение от iliya785

а лучше я их кину сюда

давай

@iliya785 · 05.06.2014, 02:11

Кинул уже на почту . Но скину вдруг кому пригадится
Алгоритм Крускала

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
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
 
struct edge{
    int a,b,c;
};
 
vector <int> parent(100001);
vector <edge> q(100001);
long long ans = 0;
 
bool cmp(edge a,edge b){
    return a.c < b.c;
}
 
int find_set(int v){
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
 
void union_sets(int a,int b,int c){
    a = find_set(a);
    b = find_set(b);
    if (a != b){
        parent[b] = a;
        ans += c;
    }
}
 
int main(){
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        parent[i] = i;
    int m = -1,x;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j){
                scanf("%d",&x);
                if (x){
                    q[++m].a = i;
                    q[m].b = j;
                    q[m].c = x;
                }
        }
    sort(q.begin(),q.begin()+m,cmp);
    for (int i=0;i<m;++i)
        union_sets(q[i].a,q[i].b,q[i].c);
    printf("%d\n",ans);
}

P.S. Только измени название темы

Добавлено через 43 секунды
Алгоритм Флойда

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
 
int main(){
    cin.sync_with_stdio(false);
    int n;
    cin>>n;
    int w[n][n];
    for (int i=0;i<n;++i)
        for (int j=0;j<n;++j){
            cin>>w[i][j];
            if (!w[i][j])   w[i][j] = 1000*1000*1000;
        }
    for (int k=0;k<n;++k)
        for (int i=0;i<n;++i)
            for (int j=0;j<n;++j)
                w[i][j] = min(w[i][j],w[i][k] + w[k][j]);
    for(int i=0;i<n;++i)
        w[i][i] = 0;
    int l,r;
    cin>>l>>r;
    cout<<w[--l][--r]<<endl;
}

Добавлено через 54 секунды
Форда-Фалкерсона(max поток)

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
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
 
const int inf = 1000*1000*1000;
 
int main(){
    int n,m,u,v,w,s,t;
    scanf("%d%d",&n,&m);
    int c[11][11],f[11][11];
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            c[i][j] = f[i][j] = 0;
    for (int i=0;i<m;++i){
        scanf("%d%d%d",&u,&v,&w);
        c[u][v] = w;
    }
    scanf("%d%d",&s,&t);
    for (;;){
        vector < int > p(11),cf(11);
        queue < int > q;
        q.push(s); cf[s] = inf;
        while (!q.empty()){
            int v = q.front();
            for (int i=1;i<=n;++i){
                if (!p[i] && c[v][i] - f[v][i] > 0){
                    q.push(i);
                    p[i] = v;
                    cf[i] = min(cf[v],c[v][i] - f[v][i]);
                }
            }
            q.pop();
        }
        if (!p[t])  break;
        for (int u=t;u != s;u = p[u]){
            f[p[u]][u] += cf[t];
            f[u][p[u]] -= cf[t];
        }
    }
    long long flow = 0;
    for (int i=1;i<=n;++i)
        if (c[s][i] > 0)
            flow += f[s][i];
    printf("%d\n",flow);
}

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	05.06.2014, 01:19
	ответ абсолютно верный - и там и там вес 65(вес кратчайшего пути и там и там я проверил ) Кратчайший путь в звешенном графе определяется суммой всех рёбер входящих в этот путь, просто в этом графе несколькократчайших путей. Добавлено через 3 минуты для проверки я менял матрицу , поэтому в разных вариантах разные матрицы , используй послелний вариант Добавлено через 48 секунд перепроверь матрицу Добавлено через 1 минуту а какой должен быть для 60 напиши плс Добавлено через 5 минут Скажи какой путь кратчайший путь. Перепроверь матричку(я её менял и не один раз). 0

@Aecttann 6 / 6 / 5 Регистрация: 19.10.2013 Сообщений: 359
	05.06.2014, 01:20 [ТС]
	для 60 кратчайший путь 0-1-5-4-7-9 0-20-30-45-50-60 Добавлено через 54 секунды Матрицу перепроверил 0

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

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

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	05.06.2014, 01:52
	d - массив расстояний , p - предков , used - посещений, g[][] - матрица смежности. P.S. На вы можно и не обращаться сам студент , только недавно подобное сдавал, если нужны реализации других алгоритмов по этой дисциплине могу скинуть :-) Добавлено через 2 минуты 1 объявление большой константы (типа бесконечность) 2 объявление массивов (выше описно какие именно) 3 Алгоритм Дейкстры 4 Восстановление пути 0

@Aecttann 6 / 6 / 5 Регистрация: 19.10.2013 Сообщений: 359
	05.06.2014, 01:57 [ТС]
	спасибо Не по теме: дискретка она такая))) кидай всё, что есть))) сейчас в лс мыло кину Добавлено через 3 минуты iliya785, Не по теме: или не скину мыло... iliya785 has chosen not to receive private messages or may not be allowed to receive private messages. 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	05.06.2014, 02:00
	а лучше я их кину сюда 0

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

Решение