Алгоритм топологической сортировки или "поиск кратчайших путей на графах"

@Krovonovskiy · Регистрация: 18.02.2016

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

Добрый день, помогите пожалуйста разобраться с алгоритмом топологической сортировки, суть в том, что с самим алгоритмом разобрался, всё работает, но кратчайший путь выбирается только по первому шагу, т.е. если граф начинает путь с x1 и идёт через x3 и потом к x2, то получается 7, но нужно сделать так, чтобы он выбирал кратчайший путь, т.е. от x1 к x2 . Как это можно сделать?

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
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
 
int main()
{
    system("chcp 1251 > NULL");
 
    int i,j,k,n=7,t,max,c[n][n],p[n],pl[n],l[n],cl[n][n];
 
    printf("\nLaboratornaya rabota 1");
    printf("\nISp.1-17-1");
    printf("\nKucherov Vladislav");
    printf("\n");
    printf("\n");
 
    printf("Нажмите Enter, чтобы запустить программу\n");
    getch();
    printf("\n");
 
    for(i=0;i<n;i++) //построение массива
        for(j=0;j<n;j++)
            c[i][j]=0;
 
  c[0][1]=8; c[0][2]=4; //заполнение массива числ. знач-ми (графа)
  c[1][3]=8; c[1][4]=3;
  c[2][1]=3; c[2][3]=10;
  c[2][5]=12; c[3][5]=3;
  c[4][3]=2; c[4][6]=10;
  c[5][6]=4;
 
    printf("Матрица весов графа:\n");
    for(i=0;i<n;i++)
 
    {
        for(j=0;j<n;j++)
            printf(" %2d",c[i][j]);
        printf("\n");
    }
 
    for(i=0;i<n;i++) //создание копии массива
        for(j=0;j<n;j++)
            cl[i][j]=c[i][j];
 
    max=0;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            max+=c[i][j];
 
    //НАЧАЛО АЛГОРИТМА ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ
    for(k=0;k<n;k++)
    {
        for(i=n-1;i>=0;i--)
            {
                t=0;
                for(j=0;j<n;j++)
                    if(cl[i][j]==0)
                        t++;
                    if(t==n-k)
                        break;
            }
            p[n-k-1]=i;
            for(j=0;j<n;j++)
                cl[i][j]=cl[j][i]=-1;
    }
    //КОНЕЦ АЛГОРИТМА ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ
    
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cl[i][j]=c[i][j];
 
    for(i=0;i<n;i++)
        l[i]=0;
 
    for(i=1;i<n;i++)
    {
        t=p[i];
        for(j=0;j<n;j++)
            if(cl[j][t]!=0)
                cl[j][t]+=l[j];
        k=max;
        for(j=0;j<n;j++)
            if(k>cl[j][t]&&cl[j][t]!=0)
                k=cl[j][t];
        l[t]=k;
    }
 
    printf("\n");
    printf("Длина кратчайшего пути = %d",l[n-1]);
    printf("\n");
 
    for(i=0;i<n;i++)
        pl[i]=0;
    pl[n-1]=p[n-1]+1;
    for(i=n-1;i>0;i--)
    {
        for(j=0;j<n;j++)
            if(l[p[i]]-l[p[i-1]]==c[j][p[i]])
                pl[i-1]=j+1;
    }
 
    k=0;
    for(i=0;i<n-1;i++)
        if(pl[i]==0)
        {
            for(j=i;j>0;j--)
            {
                t=pl[j];
                pl[j]=pl[j-1];
                pl[j-1]=t;
            }
            k++;
        }
 
    printf("Найденный кратчайший путь: (");
    for(i=k;i<n;i++)
    {
        printf("X%d",pl[i]);
        if(i!=n-1)
            printf(",",pl[i]);
    }
            printf(")");
            printf("\n");
    }

@Vladimir. · 20.10.2020, 04:25

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

//построение массива
//создание копии массива

memset и memcpy же есть, либо int c[n][n] = {0};

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

топологической сортировки

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

нужно сделать так, чтобы он выбирал кратчайший путь, т.е. от x1 к x2

И где в этом случае должна быть $https://www.cyberforum.ru/cgi-bin/latex.cgi? X_3$ ?

Добавлено через 1 час 4 минуты
Ну, про x3 я положим понял - не сразу сообразил, что вы еще и путь ищете.
Зачем вы так не любите своего препода, первокурсниуц которой отдадите решение и нас? Я не прошу функций/подпрограмм, но неужели сложно было сделать хотя бы так:

C
1
2
3
4
5
6
7
8
    int i,j,k,n=7,t,max,c[n][n],p[n],pl[n],l[n],cl[n][n];
    /*
    c[n][n], - матрица смежности
    p[n], - топологически отсортированные индексы вершин
    pl[n], - индексы вершин кратчайшего пути
    l[n], - что-то не понятное. Пока что. 
    cl[n][n]; - копия матрицы смежности для сортировки
    */

Глубокий смысл этих действий ускользает от меня. Что здесь происходит?:

C
1
2
3
4
5
6
7
8
9
10
11
12
    for(i=1;i<n;i++)
    {
        t=p[i];                    // вершина для перехода, зачем?
        for(j=0;j<n;j++)
            if(cl[j][t]!=0)        // есть ребро из j в t? Почему в j->t а не t->j?
                cl[j][t]+=l[j];    
        k=max;
        for(j=0;j<n;j++)                 //это намеренная обфускация кода?
            if(k>cl[j][t]&&cl[j][t]!=0) //блин, вы же просто минимум ищете!
                k=cl[j][t];                   //неужели нельзя по человечески написать?
        l[t]=k;                    //ах, вот зачем. А почему вверху а не здесь? l[p[i]] = k;
    }

@Exp2dot7 · 20.10.2020, 06:24

а что важнее?

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

Алгоритм топологической сортировки

или

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

"поиск кратчайших путей на графах"

понимаю, что одно другому не противоречит, но совмещать обязательно?

@Vladimir. · 20.10.2020, 13:54

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

совмещать обязательно?

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

@Krovonovskiy · 21.10.2020, 16:57 **[ТС]**

Прошу прощения, но в программировании полный 0 (почти), могу брать и адаптировать под себя (лабораторную мне сдавать), с другого языка переписывал под С (на другой никак), поэтому глубокий смысл ускользает не только от вас, прошу прощения что всё так плохо, но что-либо попытаться спросить чтобы облегчить себе жизнь тоже хочется

@Exp2dot7 · 21.10.2020, 18:55

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
#define N 7
int g[][N]={
    { 0, 7, 4, 0, 0, 0, 0},
    { 0, 0, 0, 8, 3, 0, 0},
    { 0, 3, 0,10, 0,12, 0},
    { 0, 0, 0, 0, 0, 3, 0},
    { 0, 0, 0, 2, 0, 0,10},
    { 0, 0, 0, 0, 0, 0, 4},
    { 0, 0, 0, 0, 0, 0, 0}};
int a[N]={0},b[N]={0},f[N]={0};
int mx;
void dfs(int n,int idx,int s)
{
    int i;
    if(s>=mx) return;
    a[idx]=n+1;
    if(n==N-1)
    {
        mx=s;
        memmove(b,a,N*sizeof(int));
    }
    else
        for(i=0; i<N; i++)
            if(g[n][i] && !f[i])
            {
                f[i]=1;
                dfs(i,idx+1,s+g[n][i]);
                f[i]=0;
            }
    a[idx]=0;
}
int main(int argc, char** argv)
{
    int i;
    mx=INT_MAX;
    dfs(0,0,0);
    for(i=0; i<N && b[i]; i++)
    {
        if(i) printf("(%d)->",g[b[i-1]-1][b[i]-1]);
        printf("%d",b[i]);
    }
    printf(" (%d)\n",mx);
    system("pause");
    return 0;
}

@Krovonovskiy · 23.10.2020, 16:48 **[ТС]**

Спасибо большое! Постараюсь разобраться

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@Krovonovskiy 0 / 0 / 0 Регистрация: 18.02.2016 Сообщений: 19
	21.10.2020, 16:57 [ТС]
	Прошу прощения, но в программировании полный 0 (почти), могу брать и адаптировать под себя (лабораторную мне сдавать), с другого языка переписывал под С (на другой никак), поэтому глубокий смысл ускользает не только от вас, прошу прощения что всё так плохо, но что-либо попытаться спросить чтобы облегчить себе жизнь тоже хочется 0

@Krovonovskiy 0 / 0 / 0 Регистрация: 18.02.2016 Сообщений: 19
	23.10.2020, 16:48 [ТС]
	Спасибо большое! Постараюсь разобраться 0