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

Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Определите количество участников состязаний, которые разделили первое место http://www.cyberforum.ru/cpp-beginners/thread1102839.html
Состязания. Если перенумеровать спортсменов числами от 0 до n-1, а попытки каждого из них – от 0 до m-1, то на вход программа получает массив int A, состоящий из неотрицательных чисел. Будем считать, что победитель определяется по лучшему результату. Определите количество участников состязаний, которые разделили первое место, то есть определите количество строк в массиве, которые содержат...
C++ Работа с классами (сделать, чтобы функция возвращала массив, получаемый суммированием двух входных) В программу передаю 2 массива из пяти чисел. После выполнения функции getAM хочу, чтобы она возвращала массив, получаемый суммированием двух входных. Сейчас, она выводит только первый элемент. Подскажите, что нужно исправить.#include <iostream> using namespace std; class demodulator { public: demodulator(int* ,int*); ~demodulator(void); int AM(void); http://www.cyberforum.ru/cpp-beginners/thread1102825.html
C++ Рекурсивная программа, печатающая n-ое простое число.
Напишите, пожалуйста, рекурсивную программу, печатающую n-ое простое число.
Определить число латинских букв в строке C++
Я не знаю как сделать эту задачу. Прошу помочь.
C++ Запуск и последующее удаление всех исполняемых файлов из каталога http://www.cyberforum.ru/cpp-beginners/thread1102776.html
Здравствуйте. Прошу помочь написать программу, которая бы запускала все исполняемые файлы (.exe, .bat, .cmd) из заданного каталога, а потом удаляла их. Как запустить исполняемый файл мне понятно, как удалить его вроде бы тоже. Вопрос вот в чем: как сделать это именно из каталога и с файлами с определенным расширением? Я правильно понял, что нужно использовать Get и SetCurrentDirectory? Или...
C++ Добавление элемента в линейный список после 1-го, 3-го, 5-го и т.д Помогите пожалуйста, нужно написать функцию добавления в линейный список заданного элемента после 1-го, 3-го, 5-го и т.д. подробнее

Показать сообщение отдельно
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
22.02.2014, 20:18     Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла
saroff, держи
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
#include <cstdio>
using namespace std;
 
const int N = 100; // max количество вершин в графе
const int INF = 1000000; // бесконечное расстояние, указывает на то, что между вершинами нет пути
 
int n; // кол-во вершин в графе
int adj[ N ][ N ] = { { 0 } }; // матрица смежности
int path[ N ][ N ]; // матрица путей
int dist[ N ][ N ]; // матрица расстояний
 
void read_graph()
{
// граф считывается следующим образом: сначала считывается кол-во вершин и кол-во ребер,
// а затем ребра в следующем формате: <начальная вершина> <конечная вершина> <расстояние между ними>
// замечание: данная функция считывает орграф
    int m;
 
    scanf( "%d%d", &n, &m );
    for ( int u, v, w; m--; adj[ u ][ v ] = w )
        scanf( "%d%d%d", &u, &v, &w );
}
 
void floid()
{
// инициализация матриц путей и расстояний
    for ( int u = 0; u < n; ++u )
        for ( int v = 0; v < n; ++v )
            if ( adj[ u ][ v ] || u == v )
            {
                path[ u ][ v ] = v;
                dist[ u ][ v ] = adj[ u ][ v ];
            }
            else
            {
                path[ u ][ v ] = N;
                dist[ u ][ v ] = INF;
            }
 
// сам алгоритм флойда
    for ( int k = 0; k < n; ++k )
        for ( int u = 0; u < n; ++u )
            if ( dist[ u ][ k ] != INF )
                for ( int v = 0; v < n; ++v )
                    if ( dist[ u ][ v ] > dist[ u ][ k ] + dist[ k ][ v ] )
                    {
                        dist[ u ][ v ] = dist[ u ][ k ] + dist[ k ][ v ];
                        path[ u ][ v ] = path[ u ][ k ];
                    }
}
 
void show_path( int u, int v )
{
// вывод пути из вершины u в v и расстояния между ними 
    if ( path[ u ][ v ] == N )
    {
        printf( "No path\n" );
        return;
    }
 
    int x = u;
 
    printf( "%d", x );
    while ( x != v )
        printf( " %d", x = path[ x ][ v ] );
    printf( " (%d)\n", dist[ u ][ v ] );
}
 
int main()
{
    int u, v;
 
    read_graph();
    floid();
 
    while ( true ) // обрабатываем запросы вывода путей и расстояний между вершинами пока не нажато ctrl-Z (ну или ctrl-D)
    {
        printf( "Enter source and destination vertices: " );
        if ( EOF == scanf( "%d%d", &u, &v ) )
            break;
        show_path( u, v );
    }
 
    return 0;
}
 
Текущее время: 15:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru