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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
bohdan_si
12 / 12 / 2
Регистрация: 03.10.2012
Сообщений: 83
#1

Нахождение кратчайшего пути в графе, алгоритм Уоршелла - C++

15.10.2013, 14:49. Просмотров 1323. Ответов 1
Метки нет (Все метки)

Привет всем!
алгоритм уоршелла, нужно найти кратчайший путь в графе.
ввожу матрицу
C++
1
2
3
0 1 5
1 0 2
5 2 0
работает нормально, все вершины связаны, эсли уже брать граф где нет соединение между 2,3.... вершинами работает не корректно.
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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
using namespace std;
int main()
{   
setlocale(LC_ALL,"rus");
   int n;
   cout<<"Размер массива: \n";
   cin>>n;
   int mat1[n][n],mat2[n][n];
   for(int tp=0;tp<n;tp++){
        for(int tp1=0;tp1<n;tp1++){
            cin>>mat1[tp][tp1];
        }
   }
   for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                        mat1[i][j] = min(mat1[i][j], mat1[i][k] + mat1[k][j]);
                }   
        }       
   }
   for(int t2p=0;t2p<n;t2p++){
        cout<<"\n";
        for(int t2p1=0;t2p1<n;t2p1++){
            cout<<mat1[t2p][t2p1]<<" ";
   }    }
   system("PAUSE");
}
Нахождение кратчайшего пути в графе, алгоритм Уоршелла
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.10.2013, 14:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нахождение кратчайшего пути в графе, алгоритм Уоршелла (C++):

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной - C++
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие...

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

Восстановление кратчайшего пути в графе - C++
Есть алгоритм нахождения кратчайших путей(Флойд), а как восстановить путь как узнать через какие вершины он прошел?туплю прогаю с утра)) ...

Поиск кратчайшего пути на графе - C++
Выдает ошибку Error 1 error C4996: 'itoa': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _itoa. See...

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

Поиск кратчайшего пути в графе - C++
Добрый вечер! Помогите решить задание пожалуйста: написать программу, решающую задачу в соответствие с вариантом, и вывести результат...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
XRoy
852 / 702 / 217
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
15.10.2013, 17:59 #2
Возможно причина в том что вы вводите расстояние равное 0, и считаете что это указывает на отсутствие пути. Вам нужно взять достаточно большое число которое указывает на отсутствие пути. К примеру максимальное значение int деленное пополам.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.10.2013, 17:59
Привет! Вот еще темы с ответами:

Нахождение кратчайшего пути - C++
Нужно сделать программу,чтоб она находила кратчайший путь от города 1 до города 2 на карте. Как реализовать в коде не знаю, помогите. ...

Нахождение кратчайшего пути, поиск с возвратом - C++
Описание проблемы: Есть матрица MxN, на матрицы есть дом школьника и школа. Школьник может двигаться в 4 направления. На прохождения 1ой...

Нахождение кратчайшего пути от одной вершины графа до другой - C++
Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей #include &lt;iostream.h&gt; #include...

Нахождение кратчайшего пути по матрице, или передвижение привидений в игре Пакмен - C++
Подскажите пожалуйста как правильно реализовать? Имеются координаты x,y пакмана и приведения. Я использую такой алгоритм: void...


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

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

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