Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Alex_Reilly
0 / 0 / 0
Регистрация: 04.12.2011
Сообщений: 26
1

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

28.03.2012, 22:15. Просмотров 1559. Ответов 0
Метки нет (Все метки)

Задание:
Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
Пример:
4
0 5 9 -1
-1 0 2 8
-1 -1 0 7
4 -1 -1 0

Должно получится "16", а у меня получается в ответе "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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
#define M 123456789
 
int main()
{
    setlocale(LC_ALL, "rus");
    int V_min, TS = M, S, N, A[100][100] = {};
    cout<<"Введите количество вершин:\n";
    cin >> N; // Ввод количества вершин
    // Ввод матрицы 
    cout<<"Введите элементы матрицы смежности:\n";
    for ( int i = 0; i < N; ++i )
        {
        for ( int j = 0; j < N; ++j )
            {
            cin >> A[i][j];
            if ( A[i][j] < 0 )
                {
                A[i][j] = M;
                }
            }
        }
    // Алгоритм Флойда-Уоршелла
    for ( int k = 0; k < N; ++k )
        {
        for ( int i = 0; i < N; ++i )
            {
            for ( int j = 0; j < N; ++j )
                {
                A[i][j] = min (A[i][j], A[i][k] + A[k][j]);
                }
            }
        }
             
    // Ищем вершину с минимальной суммой
 
    for ( int i = 0; i < N; ++i )
    {
       S = 0;
        for ( int j = 0; j < N; ++j )
            {
            S += A[i][j];
            }
            if ( S < TS )
                {
                TS = S;
                V_min = i;
                }
    }
    cout << V_min; 
    system("pause");
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.03.2012, 22:15
Ответы с готовыми решениями:

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой
В первой строке содержатся три числа: N, S и F (1≤N≤100, 1≤S,F≤N), где N — количество вершин графа,...

Определить номера вершин графа, в которых пересекаются кратчайшие пути из вершин
Дано взвешенный граф в котором насчитывается N вершин и M ребер. Необходимо определитить номера...

Изобразить четырехугольник, вращающийся в плоскости экрана вокруг одной из своих вершин. Цвет фона, координаты вершин и
Нужно сделать и забыть, а разобраться толком не могу, помогите пожалуйста Вот задание :...

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

Из всех пар простых чисел, сумма которых равна заданному числу, найти пару, содержащую наименьшее простое число
Известно, что любое чётное число, большее 2, представимо в виде суммы 2 простых чисел, причём таких...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.03.2012, 22:15

Найти координаты всех вершин параллелограмма, если известны координаты одной вершины и уравнения двух его сторон
Найти координаты всех вершин параллелограмма, если известны координаты одной вершины А=(12;-7) и...

Как найти число вершин и ребер в графе окресности каждой пары вершин
Как найти число вершин и ребер в графе окресности каждой пары вершин? Добавлено через 5 минут В...

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


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

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

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