2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
1

Алгоритм Флойда. Восстановить пути

15.12.2012, 15:08. Показов 3846. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
У меня есть рабочий алгоритм Флойда, он выводит все пути и максимальный путь, необходимо восстановить этот максимальный путь. Т.е. вывести все вершины, которые входят в данный путь. Я знаю, что для этого нужно завести массив, но вот как его заполнять и выводить не могу сообразить.Я созад массив p, подскажите, как заполнить его.
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
//флойд
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ofstream out ("output.txt");
ifstream in ("input.txt");
int main()
{
    int n,temp,st,sd;
    in >> n;
vector<vector<int>> a(n);
int p[100][100];
    for (int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            in >> temp;
            a[i].push_back(temp);
        }
    for (int k=0;k<n;k++)
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
            {   
                if(a[i][j]>a[i][k]+a[k][j])
                {
                    a[i][j]=a[i][k]+a[k][j];
                }
            }
    int max=-1;
    for (int i=0;i<n;i++)
    {
      for (int j=0;j<n;j++)
      {
        if(i==j)
            a[i][j]=-1;
        out << a[i][j] << " ";
      }
      out << '\n';
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(max<a[i][j])
            {
                max=a[i][j];
                st=i;
                sd=j;
            }
    out<<"самый длинный путь из "<<st+1<<" в "<<sd+1<<" = "<<max<<endl;
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.12.2012, 15:08
Ответы с готовыми решениями:

Алгоритм Флойда - Уоршала с восстановлением пути
Написать многопоточный поиск, реализован алгоритм Флойда - Уоршала. Даны два потока, в которых...

Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда.
Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. А л г о р и т м Ф...

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

Алгоритм Флойда
Добрый вечер, помогите исправить ошибки в коде. #include &lt;iostream&gt; #include &lt;time.h&gt; #include...

0
15.12.2012, 15:08
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.12.2012, 15:08
Помогаю со студенческими работами здесь

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru