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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Покупатели продуктового магазина пользуются 10% http://www.cyberforum.ru/cpp-beginners/thread1180997.html
Помогите решить пожалуйста, вообще не знаю как решить( Покупатели продуктового магазина пользуются 10% скидкой, если покупка состоит из более чем 5 наименований товаров или суммарная стоимость покупки превышает K рублей. Составить ведомость, учитывающую скидки: покупатель, количество наименований купленных товаров, стоимость покупки, стоимость покупки с учетом скидки. Выяснить, сколько...
C++ Определить периоды, когда в парикмахерской свободные женские и мужские мастера Здравствуйте форумчане, у меня к вам несколько нескромная просьба, помогите мне пожалуйста, оформив эти задачи программно: и эту: "В парикмахерской обслуживания клиентов проводят по предварительной записи. Определить периоды, когда свободные женские и мужские мастера (отдельно). Определить дни, наиболее благоприятные для проведения презентации новой косметики. Исходные данные и результаты... http://www.cyberforum.ru/cpp-beginners/thread1180983.html
Перегрузка операторов, если класс содержит массив C++
Добрый день, требовалось написать прогу, которая выводит количество повторений элементов в массиве, причем сделать это требовалось с помощью объектов, т.е. должно быть два объекта поставщика, один из них для ввода с клавы, а другой чтения с файла. и есть Объект чей метод подсчета получает информацию от данных объектов поставщиков. Собственно, большинство я сделал, и прога работает, но...
C++ Выравнивание текста пробелами по ширине.
Очень нужно написать решение на C++. Кто-нибудь может помочь? Я пытался 2 дня - ничего не получается :( Задача Вашей программе дается абзац текста. Этот текст состоит из ряда слов, отделенных друг от друга пробелами и/или символами новой строки (символы табуляции не применяются). Слово может содержать знаки пунктуации. Текст завершается специальным словом "$$$", которое будет единственным...
C++ Вычислить сумму ряда http://www.cyberforum.ru/cpp-beginners/thread1180947.html
4. 4.3. Написать программу, позволяющую вычислить с помощью цикла: 2+4+6+…+2n, где n задается с клавиатуры.
C++ Написать программу, проверяющую, поместится ли круг в квадрат или наоборот. 3. Заданы круг площади S и квадрат площади Р. Написать программу, проверяющую, поместится ли круг в квадрат или поместится ли квадрат в круг, или они не поместятся друг в друга. подробнее

Показать сообщение отдельно
zhekson94
0 / 0 / 0
Регистрация: 19.05.2014
Сообщений: 1
19.05.2014, 16:44     Алгоритм Дейкстры
Привет всем. Делаю для курсовой поиск кратчайшего пути по алгоритму Дейкстры на 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");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru