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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Нюша123
1 / 1 / 0
Регистрация: 11.10.2013
Сообщений: 63
#1

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

17.10.2013, 17:24. Просмотров 980. Ответов 5
Метки нет (Все метки)

Ребят,кто-нибудь помогите решить задачку, используя алгоритм Дейкстры.Он есть готовый,осталось с помощью него только решить.
Задача об автобусном сообщении по краю
Имя входного файла 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2013, 17:24     Задача с использованием алгоритма Дейкстры
Посмотрите здесь:

Выкладываю реализацию алгоритма Дейкстры на С++ C++
Вывод map через ostream_iterator с использованием алгоритма reverse_copy!!! C++
Задача на алгоритм Дейкстры (как лучше хранить информацию?) C++
C++ Организовать расчет полинома с использованием алгоритма Горнера
C++ Параллельная реализация алгоритма Дейкстры
C++ Реализация алгоритма Дейкстры
C++ Нахождение интервала унимодальности с использованием алгоритма Свенна
C++ Минимизировать функцию с использованием генетического алгоритма
Определение радиуса и соответствующего радиусу пути взвешенного орграфа на основе алгоритма Дейкстры C++
C++ Не найден заголовочный файл в реализации алгоритма Дейкстры
C++ Найти и исправить ошибки в реализации алгоритма Дейкстры
C++ Реализация алгоритма Хаффмана с использованием классов

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
201 / 145 / 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
_
201 / 145 / 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
_
201 / 145 / 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     Задача с использованием алгоритма Дейкстры
Ответ Создать тему
Опции темы

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