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

Алгоритм Дейкстры - C++

Восстановить пароль Регистрация
 
zhekson94
0 / 0 / 0
Регистрация: 19.05.2014
Сообщений: 1
19.05.2014, 16:44     Алгоритм Дейкстры #1
Привет всем. Делаю для курсовой поиск кратчайшего пути по алгоритму Дейкстры на C++, все сделал вот только преподаватель требует чтобы програма в показывала путь на самой матрице. А я в толк не могу взять как это сделать, помогите...

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
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
 
using namespace std;
 
#define word unsigned int
 
int i, j, n, p, xn, xk;
int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
 
int min(int n)
{
    int i, result;
    for (i = 0; i<n; i++)
    if (!(flag[i])) result = i;
    for (i = 0; i<n; i++)
    if ((l[result]>l[i]) && (!flag[i])) result = i;
    return result;
}
 
word minim(word x, word y)
{
    if (x<y) return x;
    return y;
}
 
void main()
{
    cout << "Vvedite kolichestvo tochek: ";
    cin >> n;
    for (i = 0; i<n; i++)
    for (j = 0; j<n; j++) c[i][j] = 0;
    for (i = 0; i<n; i++)
    for (j = i + 1; j<n; j++)
    {
        cout << "Vvedite rasstoyanie ot  x" << i + 1 << " do x" << j + 1 << ": ";
        cin >> c[i][j];
    }
    cout << "   ";
    for (i = 0; i<n; i++) cout << "    X" << i + 1;
    cout << endl << endl;
    for (i = 0; i<n; i++)
    {
        printf("X%d", i + 1);
        for (j = 0; j<n; j++)
        {
            printf("%6d", c[i][j]);
            c[j][i] = c[i][j];
        }
        printf("\n\n");
    }
    for (i = 0; i<n; i++)
    for (j = 0; j<n; j++)
    if (c[i][j] == 0) c[i][j] = 65535; //бесконечность
    cout << "Vvedite nachalnuy tochku: ";
    cin >> xn;
    cout << "Vvedite konechnuy tochku: ";
    cin >> xk;
    xk--;
    xn--;
    if (xn == xk)
    {
        cout << "Nachalnaya I konechnaya tochki sovpadayt." << endl;
        getchar();
        return;
    }
 
    for (i = 0; i<n; i++)
    {
        flag[i] = 0;
        l[i] = 65535;
    }
    l[xn] = 0;
    flag[xn] = 1;
    p = xn;
    _itoa_s(xn + 1, s, 10);
    for (i = 1; i <= n; i++)
    {
        strcpy_s(path[i], "X");
        strcat_s(path[i], s);
    }
    do
    {
        for (i = 0; i<n; i++)
        if ((c[p][i] != 65535) && (!flag[i]) && (i != p))
        {
            if (l[i]>l[p] + c[p][i])
            {
                _itoa_s(i + 1, s, 10);
                strcpy_s(path[i + 1], path[p + 1]);
                strcat_s(path[i + 1], "-X");
                strcat_s(path[i + 1], s);
            }
            l[i] = minim(l[i], l[p] + c[p][i]);
        }
        p = min(n);
        flag[p] = 1;
    } while (p != xk);
    if (l[p] != 65535)
    {
        cout << "Put: " << path[p + 1] << endl;
        cout << "Dlina puti: " << l[p] << endl;
    }
    else
        cout << "takogo puti ne syshestvuet!" << endl;
    getchar();
    system("pause");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.05.2014, 16:44     Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры С++ C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 13:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru