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

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

Восстановить пароль Регистрация
 
bohdan_si
12 / 12 / 2
Регистрация: 03.10.2012
Сообщений: 83
15.10.2013, 14:49     Нахождение кратчайшего пути в графе, алгоритм Уоршелла #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");
}
Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.10.2013, 14:49     Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Посмотрите здесь:

C++ Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
Поиск кратчайшего пути в графе C++
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
C++ Нахождение кратчайшего пути по матрице, или передвижение привидений в игре Пакмен
Восстановление кратчайшего пути в графе C++
C++ Нахождение кратчайшего пути, поиск с возвратом
C++ Нахождение кратчайшего пути
Поиск кратчайшего пути на графе C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
XRoy
848 / 698 / 217
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
15.10.2013, 17:59     Нахождение кратчайшего пути в графе, алгоритм Уоршелла #2
Возможно причина в том что вы вводите расстояние равное 0, и считаете что это указывает на отсутствие пути. Вам нужно взять достаточно большое число которое указывает на отсутствие пути. К примеру максимальное значение int деленное пополам.
Yandex
Объявления
15.10.2013, 17:59     Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Ответ Создать тему
Опции темы

Текущее время: 10:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru