-1 / 18 / 7
Регистрация: 21.04.2019
Сообщений: 493
1

Найти максимальные пути для каждой вершины

20.11.2019, 15:37. Показов 367. Ответов 2
Метки c++ (Все метки)

Взял алгоритм Флойда-Уоршелла из сайта http://kvodo.ru/algoritm-floyda-uorshella.html
Вопрос: Как сделать так, чтобы алгоритм находил не кратчайшие пути для каждой вершины, а наоборот, самые длинные пути?

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
#include "stdafx.h"
#include <iostream>
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
//алгоритм Флойда-Уоршелла
void FU(int D[][maxV], int V)
{
int k;
for (i=0; i<V; i++) D[i][i]=0;
 
for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
D[i][j]=D[i][k]+D[k][j];
 
for (i=0; i<V; i++)
{
for (j=0; j<V; j++) cout<<D[i][j]<<"\t";
cout<<endl;
}
}
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
cout<<"Количество вершин в графе > "; cin>>n;
cout<<"Введите матрицу весов ребер:\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<"GR["<<i+1<<"]["<<j+1<<"] > ";
cin>>GR[i][j];
}
cout<<"Матрица кратчайших путей:"<<endl;
FU(GR, n);
system("pause>>void");
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.11.2019, 15:37
Ответы с готовыми решениями:

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

Найти максимальные элементы каждой строки матрицы
Дан двумерный массив А. Массив В(5) нужно построить следующим образом: к массиву B(j) нужно...

Найти максимальные элементы каждой строки матрицы и просуммировать их
Помогите, надо найти сумму, всё остальное вроде получилось: #include &lt;iostream&gt; #include &lt;time.h&gt;...

Найти максимальные элементы каждой строки двумерной матрицы
составить программу, которая находит максимальные элементы каждой строки двумерной матрицы A,...

2
6565 / 4550 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
20.11.2019, 15:57 2
Цитата Сообщение от Олег1000 Посмотреть сообщение
Вопрос: Как сделать так, чтобы алгоритм находил не кратчайшие пути для каждой вершины, а наоборот, самые длинные пути?
Попробуй поменять знак меньше на знак больше if (D[i][k]+D[k][j] > D[i][j] || D[i][j]==0)
0
-1 / 18 / 7
Регистрация: 21.04.2019
Сообщений: 493
21.11.2019, 05:24  [ТС] 3
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Попробуй поменять знак меньше на знак больше if (D[i][k]+D[k][j] > D[i][j] || D[i][j]==0)
Не то
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.11.2019, 05:24
Помогаю со студенческими работами здесь

Найти максимальные элементы в каждой строке матрицы и отсортировать их по убыванию
Как написать такой код ? Дано матрицу В(4,4) Найти максимальные елементы в каждой строке и...

Графы: заданы две вершины, начальная и конечная, требуется найти первую вершину в пути между ними
Задан граф матрицей смежности Заданы две вершины, начальная и конечная, требуется найти первую...

Найти степени входа и выхода каждой вершины графа.
Задано множество упорядоченных пар вершин, соответствующих дугам ориентированного графа. Найти...

Найти максимальные и минимальные элементы в каждой строке и каждом столбце заданной целочисленной матрицы
Помогите, пожалуйста, написать программу, вычисляющую максимальные и минимальные элементы в каждой...


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

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

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