Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.70/130: Рейтинг темы: голосов - 130, средняя оценка - 4.70
White Luna
33 / 27 / 2
Регистрация: 08.09.2010
Сообщений: 402
1

Алгоритм Флойда - Уоршелла

13.12.2010, 18:07. Просмотров 23764. Ответов 13
Метки нет (Все метки)

не получается реализовать алгоритм Флойда-Уоршелла, вроде все должнен выводить, а выводит или нули или вообще ничего, ошибок не выводит не понимаю в чем дело.
вот код проги
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
#include "stdafx.h"
#include "iostream"
#include "string.h"
#include "conio.h"
#include "stdlib.h"
#include "stdio.h"
 int d[4][4];
using namespace std;
 
int main()
{
 
    FILE *p, *v;
    int i, j, m, k;
    const int n=4;
// ввод исходных данных
    p=fopen("vxod.txt", "r");
    if(p == 0)
    {
        printf("Невозможно открыть данный файл 's'", "vxod.txt");
        return 0;
    };
    while ((m=getc(p))!=EOF)
        putchar(m);
// ввод исходных данных закончен
 
for (int k=0; k<n; ++k)
{
    for (int i=0; i<n; ++i)
    {
            for (int j=0; j<n; ++j)
            {
            d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
            cout << d[i][j];
            }
        
    }
}
    fclose (p);
system ("\n pause");
exit(0);
_getch();
    return 0;
}
вот текст файла
4
1 0 2 3 4
2 1 0 4 3
3 1 2 0 2
4 4 3 1 0

Алгоритм Флойда-Уоршелла нахождения кратчайших путей между всеми парами вершин.

мне надо найти вершину, чтоб между нею и другими вершинами., не более 4
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2010, 18:07
Ответы с готовыми решениями:

Алгоритм Флойда–Уоршелла
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++)как сделать так,...

Алгоритм Флойда-Уоршелла (результат работы неправильный)
Задание выглядит так: Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее...

Не могу найти ошибку в алгоритме Флойда-Уоршелла
Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти...

Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла
Делаю, алгоритм флойда-уоршелла, делаю сам на делфи, но исходники с решением моей проблемы (ну по...

Алгоритм Уоршелла
#include&lt;stdio.h&gt; #include &lt;iostream&gt; const int V = 4; int i,j; void transitiveClosure(int...

13
ForEveR
В астрале
Эксперт С++
8007 / 4764 / 654
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
13.12.2010, 18:20 2
Дискретная математика
Тут ж есть алгоритм.
0
White Luna
33 / 27 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 19:03  [ТС] 3
а каким образом там массив вводится?: я чего то не поняла

Добавлено через 5 минут
я там похоже даже в вводе данных запуталась

Добавлено через 18 минут
вроде чуть разобралась там несколько алгоритмов, а который из них Флойда-Уоршелла, точнее что там к нему относится???

Добавлено через 6 минут
Как я поняла вот эти части кода относятся к тому чтоо мне надо, ? следавотельно к чему относится остальное, и надо ли оно мне? и что я упстила?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 void FindPathMatr()
        {
                for(size_t k=0; k<Matr.size(); ++k)
                {
                        for(size_t i=0; i<Matr.size(); ++i)
                        {
                                for(size_t j=0; j<Matr.size(); ++j)
                                {
                                        int b=MatrSPath[i][k]+MatrSPath[k][j];
                                        if(b<MatrSPath[i][j])
                                        {
                                                MatrSPath[i][j]=b;
                                                MatrPath[i][j]=k;
                                        }
                                }
                        }
                }
        }
C++
1
 Ob.FindPathMatr();
0
ForEveR
В астрале
Эксперт С++
8007 / 4764 / 654
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
13.12.2010, 19:23 4
White Luna, Там вся программа алгоритм Флойда Уоршалла...

Добавлено через 8 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
       void Fill()
        {
                for(size_t i=0; i<Matr.size(); ++i)
                {
                        for(size_t j=0; j<Matr.size(); ++j)
                        {
                                if(i==j)
                                        Matr[i][j]=0;
                                else if(i>j)
                                {
                                        Matr[i][j]=Matr[j][i];
                                }
                                else
                                {
                                        std::cout<<"Enter weight of V"<< i <<",V"<< j <<" edge\n"
                                                <<"0 for not connect them\n";
                                        std::cin>>Matr[i][j];
                                        if(Matr[i][j]==0)
                                                Matr[i][j]=100;
                                }
                        }
                }
        }
Это заполнение матрицы смежности.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        void Initialise()
        {
                MatrPath.resize(Matr.size());
                for(size_t i=0; i<Matr.size(); ++i)
                        MatrPath[i].resize(Matr.size());
                for(size_t i=0; i<MatrPath.size(); ++i)
                {
                        for(size_t j=0; j<MatrPath.size(); ++j)
                        {
                                if(Matr[i][j]==100)
                                        MatrPath[i][j]=100;
                                else
                                        MatrPath[i][j]=j;
                        }
                }
                Copy();
        }
Это создание матрицы путей.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
        void FindPathMatr()
        {
                for(size_t k=0; k<Matr.size(); ++k)
                {
                        for(size_t i=0; i<Matr.size(); ++i)
                        {
                                for(size_t j=0; j<Matr.size(); ++j)
                                {
                                        int b=MatrSPath[i][k]+MatrSPath[k][j];
                                        if(b<MatrSPath[i][j])
                                        {
                                                MatrSPath[i][j]=b;
                                                MatrPath[i][j]=k;
                                        }
                                }
                        }
                }
        }
Инициализация матрицы кратчайших путей нужными значениями.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
        void FindPath(size_t first, size_t second)
        {
                if(first>=MatrPath.size() || second>=MatrPath.size())
                        throw std::invalid_argument("One of nodes for searching is more than Matr size");
                ST Goals;
                Path.push(first);
                Goals.push(second);
                while(!Goals.empty())
                {
                        int u=Path.top();
                        int v=Goals.top();
                        int s=MatrPath[u][v];
                        if(v==s)
                        {
                                Path.push(v);
                                Goals.pop();
                        }
                        else
                                Goals.push(s);
                }
        }
Это нахождение пути от вершины к другой вершине. Вершины вводятся из main-а с клавиатуры. Через два стека. Не самый оптимальный алгоритм. У меня есть оптимальнее на бумаге, но переделывать пока лень.
0
13.12.2010, 19:23
White Luna
33 / 27 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 19:28  [ТС] 5
тогда можешь пояснить каким образом там идет ввод данных

Добавлено через 3 минуты
блин.... тогда по идеи мне первые 2 пункта которые ты выделил не нужны т к я матрицу смежности ввожу как файл, так меньше мороки, и более понятно, но потом у ми возникают проблемы как её определить
0
BrumbleHorse
121 / 121 / 16
Регистрация: 18.09.2010
Сообщений: 212
13.12.2010, 19:35 6
Этот алгоритм на с++ есть здесь
http://khpi-iip.mipk.kharkiv.edu/lib.../din_0100.html
все нормально работает..
0
ForEveR
В астрале
Эксперт С++
8007 / 4764 / 654
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
13.12.2010, 19:54 7
BrumbleHorse, Это не тот алгоритм. Это алгоритм Уоршалла (по ссылке), а не Флойда-Уоршалла

Добавлено через 35 секунд
White Luna, То есть матрица путей у тебя тоже прям из файла береться? оО
0
White Luna
33 / 27 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 22:45  [ТС] 8
ForEveR, у меня там тока одна матрица
0
ForEveR
В астрале
Эксперт С++
8007 / 4764 / 654
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
13.12.2010, 23:26 9
White Luna, Ну да. А матрицу путей формировать? Вообще посмотри в инете четкий алгоритм. Я делал по алгоритму который давали на лекции.
0
White Luna
33 / 27 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 23:40  [ТС] 10
нашла тут один код реализации, только не понимаю его вывод кто нить может пояснить каким образом там так считается
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
#include <iostream.h>
#define MaxNodes 4
#define B 1000
 
class Warshall
{
  private:
    unsigned Adj[MaxNodes][MaxNodes]; //Матрица смежностей.
    unsigned C[MaxNodes][MaxNodes];   //Матрица достижимости.
  public:
    void Vvod();
    void MinDlin();
    void Vyvod();
};
 
void Warshall::Vvod()
//Ввод матрицы смежностей заданного графа и ее "исправление".
{
  //Ввод матрицы смежностей заданного графа.
  cout <<"Вводите элементы матрицы смежностей по строкам:\n";
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
     {
       cout <<"Введите Adj["<< (i+1) << "]["<< (j+1) << "]: ";
       cin >> Adj[i][j];
       if (Adj[i][j]==0) C[i][j] = B;
       else  C[i][j] = Adj[i][j];
     }
}
 
void Warshall::MinDlin()
//Вычисление матрицы минимальных длин путей.
{
  for (int k=0;k<MaxNodes;k++)
   for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
       if ( C[i][j]>C[i][k]+C[k][j] ) 
              C[i][j] = C[i][k]+C[k][j];
}
 
void Warshall::Vyvod()
//Вывод матрицы минимальных длин путей.
{
  cout << "Матрица минимальных длин путей:\n";
  for (int i=0;i<MaxNodes;i++)
  {
    for (int j=0;j<MaxNodes;j++)
      cout << C[i][j] << " ";
    cout << endl;
  }
}
 
void main()
{
  Warshall A;
  A.Vvod();
  A.MinDlin();
  A.Vyvod();
}
Добавлено через 6 минут
Из-за чего получается такая матр нижняя
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Вводите элементы матрицы смежностей по строкам:
Введите Adj[1][1]: 0
Введите Adj[1][2]: 1
Введите Adj[1][3]: 2
Введите Adj[1][4]: 2
Введите Adj[2][1]: 6
Введите Adj[2][2]: 0
Введите Adj[2][3]: 4
Введите Adj[2][4]: 3
Введите Adj[3][1]: 2
Введите Adj[3][2]: 6
Введите Adj[3][3]: 0
Введите Adj[3][4]: 6
Введите Adj[4][1]: 9
Введите Adj[4][2]: 6
Введите Adj[4][3]: 6
Введите Adj[4][4]: 0
Матрица минимальных длин путей:
4 1 2 2
6 7 4 3
2 3 4 4
8 6 6 9
1
ForEveR
В астрале
Эксперт С++
8007 / 4764 / 654
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
13.12.2010, 23:43 11
White Luna, Матрица минимальных путей. Нарисуйте граф на бумаге и проверьте
0
White Luna
33 / 27 / 2
Регистрация: 08.09.2010
Сообщений: 402
14.12.2010, 00:25  [ТС] 12
как минимальные пути матрицы считаются?
0
ForEveR
В астрале
Эксперт С++
8007 / 4764 / 654
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
14.12.2010, 00:41 13
White Luna, по алгоритму. А если вручную и граф маленький в уме.
0
White Luna
33 / 27 / 2
Регистрация: 08.09.2010
Сообщений: 402
14.12.2010, 00:57  [ТС] 14
я поняла это просто мы графы не проходили, и понимаю норм тока как матрицы строятся
0
14.12.2010, 00:57
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2010, 00:57

Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2...

Алгоритм Флойда-Уоршела
Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он не выводит САМО...

Алгоритм Флойда Оршала
Найти наикратчайшее расстояние от каждой до каждой. Задание представляет собой любую матрицу 4*4....


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru