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

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

Восстановить пароль Регистрация
 
Нюша123
1 / 1 / 0
Регистрация: 11.10.2013
Сообщений: 63
17.10.2013, 17:24     Задача с использованием алгоритма Дейкстры #1
Ребят,кто-нибудь помогите решить задачку, используя алгоритм Дейкстры.Он есть готовый,осталось с помощью него только решить.
Задача об автобусном сообщении по краю
Имя входного файла input.txt
Имя выходного файла output.txt
Между городами края имеется автобусное сообщение. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.
Во входном файле записано число N - общее число городов (1 <= N <= 100). номера деревень i и j, затем количество автобусных рейсов R (0 <= R <= 10000). Затем идут описания автобусных рейсов. Каждый рейс задается номером города отправления i, , города назначения j, временем в пути до этого города (целое от 1 до 10000).
a) Найти минимальное время, которое потребуется пассажиру чтобы добраться из города I в город j. Если он не сможет с помощью указанных автобусных рейсов добраться из i в j, вывести -1.
Б) Выдать названия городов, до которых пассажир может добраться за время t.
Пример
input.txt output.txt
3
1 2 3
1 3 2
2 3 2
2 4 4
3 4 4
I=1 j=4 6 1-3-4
Из 1 за 4 в 2 и 3
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
17.10.2013, 18:04     Задача с использованием алгоритма Дейкстры #2
интересно было бы поглядеть что делает ваш готовый алгоритм Дейкстры. И вот почему.

Для решения вашей задачи нужно чтобы он заполнил массив, представляющий дерево кратчайших путей исходного графа (path), а также массив, содержащий время в пути до каждого города из исходого города i (dist).

Итак, алгоритм:
0. нужны матрица смежности для хранения карты дорог, 2 массива для хранения инфо о кратчайших путях в графе (как описано выше)
1. читаем input и заполняем матрицу смежности
2. применяем алгоритм Дейкстры, который заполнит те 2 массива
3. ответ для пункта а): время в пути - dist[ j ], сам путь восстанавливаем из массива path (правда он получится в обратном порядке, следовательно после восстановления его надо перевернуть)
4. ответ для пункта б): пробегаемся циклом по массиву dist и выводим те индексы массива, для которых dist равен искомому времени

это поможет?
Нюша123
1 / 1 / 0
Регистрация: 11.10.2013
Сообщений: 63
17.10.2013, 18:25  [ТС]     Задача с использованием алгоритма Дейкстры #3
Спасибо конечно!Нооо...я вообще плохо разбираюсь в этом Не могли б вы помочь и с кодом?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
18.10.2013, 06:28     Задача с использованием алгоритма Дейкстры #4
разбирайтесь
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 минут
Ох, оказывается программа неверно работает для некоторых графов. Ошибочка вышла. Давайте поступим так: вы предоставите граф, для которого программа неверно работает, а я скажу что исправить
Нюша123
1 / 1 / 0
Регистрация: 11.10.2013
Сообщений: 63
18.10.2013, 15:48  [ТС]     Задача с использованием алгоритма Дейкстры #5
Спасибо!В входном файле даны- номер пункта отправления, номер пункта назначения и 3 число - время в пути в часах.Вот что.то есть мне нужно перебрать графы и найти тот,при котором не работает программа,так я поняла?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
18.10.2013, 16:27     Задача с использованием алгоритма Дейкстры #6
Цитата Сообщение от Нюша123 Посмотреть сообщение
Во входном файле записано число N - общее число городов (1 <= N <= 100). номера деревень i и j, затем количество автобусных рейсов R (0 <= R <= 10000). Затем идут описания автобусных рейсов.
Цитата Сообщение от Нюша123 Посмотреть сообщение
В входном файле даны- номер пункта отправления, номер пункта назначения и 3 число - время в пути в часах.
как это связано между собой?
Цитата Сообщение от Нюша123 Посмотреть сообщение
то есть мне нужно перебрать графы и найти тот,при котором не работает программа
программа работает всегда (если придерживаться ограничений из условия задачи), она иногда выдает не самый короткий путь. я хочу чтобы вы порисовали графы (достаточно 5-7 деревень) и нашли такой, на котором программа косячит, т.е. вручную можно найти более короткий путь.
Yandex
Объявления
18.10.2013, 16:27     Задача с использованием алгоритма Дейкстры
Ответ Создать тему
Опции темы

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