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

Задача с использованием алгоритма Дейкстры - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Разработать схему алгоритма для решения задачи численного интегрирования тремя методами http://www.cyberforum.ru/cpp-beginners/thread980079.html
Разработать схему алгоритма для решения задачи численного интегрирования с использованием метода прямоугольника, метода трапеций и метода Симпсона 4х2
C++ Как создать класс, где возможно создание только одного объекта? Как создать класс, где возможно создание только одного объекта? http://www.cyberforum.ru/cpp-beginners/thread980077.html
error C2678: бинарный ">>": не найден оператор, принимающий левый операнд типа "std::basic_istream<_Elem,_Traits>" C++
Нужно из файла скачать информацию в объект. Почему у меня не получается? #include <vector> #include <string> #include <iostream> #include <fstream> #include <iterator> using namespace std; class Money{
Текст из TXT файла в строку C++
Добрый день. С++ начал учить два дня назад, поэтому прошу не пинать за глупые вопросы. Ситуация следующая: есть строка S (типа char или string, пока не разобрался в чем конкретная разница) есть файл input.txt. В input.txt введен текст (для простоты возьмем что текст находится в одной строке). Задача: нужно текст из файла input.txt присвоить строке S, чтобы с ним можно было полноценно...
C++ Чьотов Чар http://www.cyberforum.ru/cpp-beginners/thread980058.html
#include <iostream> #include <Windows.h> #include <string.h> using namespace std; int main() { WIN32_FIND_DATAA findData; string file_name; cout << "Введите имя файла или q для выхода" << endl;
C++ Инкремент при обращении (н-р к массиву) int _id_; char _string_; _string_ // Изменится ли в этом случаее _id_ или это не повлеяет на начего? подробнее

Показать сообщение отдельно
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
18.10.2013, 06:28     Задача с использованием алгоритма Дейкстры
разбирайтесь
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
#include <iostream>
#include <climits>
#include <stack>
using namespace std;
 
const int N = 101;
int graph[ N ][ N ] = { { 0 } };
 
void graph_read( int m )
{
    for ( int i = 0, v, w, t; i < m; ++i )
    {
        cin >> v >> w >> t;
        graph[ v ][ w ] = graph[ w ][ v ] = t;
    }
}
 
int path[ N ] = { 0 };
int dist[ N ] = { 0 };
 
void dijkstra( int s, int n )
{
    bool mk[ N ] = { 0 };
 
    path[ s ] = s;
    mk[ s ] = 1;
    for ( int min_v = -1, min_t, v = s; min_v != s; v = min_v )
    {
        min_v = s;
        min_t = INT_MAX;
        for ( int w = 1; w <= n; ++w )
        {
            if ( !graph[ v ][ w ] || mk[ w ] ) continue;
            if ( dist[ w ] == 0 || dist[ w ] > dist[ v ] + graph[ v ][ w ] )
            {
                dist[ w ] = dist[ v ] + graph[ v ][ w ];
                path[ w ] = v;
            }
            if ( dist[ w ] < min_t ) { min_t = dist[ w ]; min_v = w; }
        }
        if ( min_v != s ) mk[ min_v ] = 1;
    }
}
 
void print_path( int v, int w )
{
    int x = w;
    stack< int > st;
 
    st.push( x );
    while ( x != v ) st.push( x = path[ x ] );
    cout << st.top(); st.pop();
    while ( !st.empty() ) { cout << '-' << st.top(); st.pop(); }
}
 
int main()
{
    int n, m, i, j;
 
    cin >> n >> i >> j >> m;
    graph_read( m );
    dijkstra( i, n );
    cout << "a) path from " << i << " to " << j;
    if ( dist[ j ] )
    {
        cout << ": ";
        print_path( i, j );
        cout << " with duration " << dist[ j ] << endl;
    }
    else
    {
        cout << " is absent" << endl;
    }
 
    return 0;
}
условие задачи не очень понятно. потрудились бы оформить правильно. пример совершенно непонятен в плане последовательности значений N, i, j, R. и последняя строка: "Из 1 за 4 в 2 и 3" что вообще значит?

Добавлено через 10 часов 29 минут
Ох, оказывается программа неверно работает для некоторых графов. Ошибочка вышла. Давайте поступим так: вы предоставите граф, для которого программа неверно работает, а я скажу что исправить
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru