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

ошибка у флойда - C++

Восстановить пароль Регистрация
 
vetal_x
 Аватар для vetal_x
18 / 18 / 2
Регистрация: 23.01.2013
Сообщений: 350
19.05.2013, 20:25     ошибка у флойда #1
помогите найти ошибку:
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
#include <fstream>
#include <iostream>
#include <windows.h>
#include <wincon.h>
using namespace std;
ifstream f1("input.txt");
int a[20][20],i,n=9,j,k,b[20][20];
int main()
{
    SetConsoleOutputCP(1251);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            f1>>a[i][j];
            if(i!=j && a[i][j] == 0) a[i][j]= 99999;else{
                b[i][j]=j+1;}
        }
    for(k=0;k<n;k++)
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(a[i][k]+a[k][j]<a[i][j] && j!=k && i!=k && i!=j && a[i][k]<99999 && a[k][j]<99999){
                    a[i][j]=a[k][j]+a[i][k];
                    b[i][j]=k+1;
                };
    for(i=0;i<n;i++){
        for(j=0;j<n-1;j++)
            cout<<a[i][j]<<" ";
        cout<<a[i][n-1]<<"\n";
    }
    cout<<"\n";
    for(i=0;i<n;i++){
        for(j=0;j<n-1;j++)
            cout<<b[i][j]<<" ";
        cout<<b[i][n-1]<<"\n";
    }
}
входная таблица:
0 0 8 2 0 0 0 0 0
0 0 5 6 0 5 0 0 0
8 5 0 0 0 5 3 0 6
2 6 0 0 0 0 0 3 9
0 0 0 0 0 4 0 0 0
0 5 5 0 4 0 0 5 3
0 0 5 0 0 0 0 0 0
0 0 0 3 0 5 0 0 0
0 0 6 9 0 3 0 0 0
мне кажется что ошибка гдета в масиве b.
Заранее спс

Добавлено через 5 минут
а если правильно, то как вывести путь от в1 вершины в в2!!!

Добавлено через 16 минут
массив "Б" отвечает за путь
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
19.05.2013, 20:34     ошибка у флойда #2
Позволь поинтересоваться, как проявляется ошибка?
vetal_x
 Аватар для vetal_x
18 / 18 / 2
Регистрация: 23.01.2013
Сообщений: 350
19.05.2013, 20:36  [ТС]     ошибка у флойда #3
ошибки нет, просто массив "Б" не такой каким я его представлял!
Если массив "Б" правильный то как мне определить путь?
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
19.05.2013, 20:39     ошибка у флойда #4
Какой путь? Посмотри по навигатору.
vetal_x
 Аватар для vetal_x
18 / 18 / 2
Регистрация: 23.01.2013
Сообщений: 350
19.05.2013, 22:37  [ТС]     ошибка у флойда #5
путь от, например вершины i к вершине j.

Добавлено через 1 минуту
вот
таблица путей:
1 4 3 4 8 8 3 4 4
4 2 3 4 6 6 3 4 6
1 2 3 1 6 6 7 6 9
1 2 1 4 8 8 3 8 9
8 6 6 8 5 6 6 6 6
8 2 3 8 5 6 3 8 9
3 3 3 3 6 3 7 6 3
4 4 6 4 6 6 6 8 6
4 6 3 4 6 6 3 6 9
но у меня нет пути с 1-вой к 8!!

Добавлено через 4 минуты
или мне нада будет сначала найти путь к 8-мой а потом уже ити в перед?
при таком ходе алгоритма это по пути может возникнуть ещо вопросы!!!
и тогда придется использовать чергу!!!

Добавлено через 31 секунду
ПС. Стек???

Добавлено через 1 час 49 минут
народ, помогите написать функцию которая ищет путь от первой вершины(к1) к последней(к2). Завтра екзамен!!!!

Добавлено через 29 секунд
нужно делать с помощю односвязного списка!
Droom
3 / 3 / 0
Регистрация: 23.01.2011
Сообщений: 71
19.05.2013, 23:17     ошибка у флойда #6
Во вложения добавил схематический рисунок вашего графа, из которого становится видно, что путь между 1 и 8 вершинами вполне себе существует.
Насчет восстановления путей, сам написать код не успею но идея такая(merge - отдельная функция, возвращающая объединение двух векторов) Ну и список вместо вектора)
C++
1
2
3
4
5
6
7
8
9
10
11
12
vector <int> find_path(int i, int j)
{
vector<int> path;
if(b[i][j]==i)
{
 path.resize(2);
 path[0]=i;
 path[1]=j;
}else
 path=merge(find_path(i+1,b[i][j]),find_path(b[i][j],j));
return path
}
Миниатюры
ошибка у флойда  
Yandex
Объявления
19.05.2013, 23:17     ошибка у флойда
Ответ Создать тему
Опции темы

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