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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.86
nikalerka
0 / 0 / 0
Регистрация: 21.11.2010
Сообщений: 77
#1

МАТРИЦА РАССТОЯНИЙ ГРАФА - C++

16.02.2011, 23:18. Просмотров 3881. Ответов 4
Метки нет (Все метки)

Доброго времени суток!
Помогите пожалуйста! Пытаюсь написать программу, которая находила бы матрицу расстояний по матрице смежности. Обыскала всевозможные источники информации. Нашла алгоритм нахождения матрицы расстояний с помощью алгоритма Флойда.
Но программа находит матрицу расстояний не для всех графов, а если быть точной, для ограниченного числа неориентированных графов. Для орграфов не работает вовсе.
Помогите исправить программу, подскажите, где ошибки?

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
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<mem.h>
#include<iostream.h>
 
//функция нахождения минимума
int min(int a,int b)
{
if(a<b) return a;
else return b;
}
 
void main(void)
{
clrscr();
int n,i,j,k,m;
cout<<"Razmer massiva:"<<endl;
cin>>n;
 
//создаю динамический массив размера n*n
int **mat=new int*[n];
 
for(k=0;k<n;k++)
mat[k]=new int[n];
 
cout<<"Vvedite matricy smegnosti:"<<endl;
for(i=0;i<n;i++)
 for(j=0;j<n;j++)
   cin>>mat[i][j];
   cout<<endl;
 
//сам алгоритм поиска матрицы расстояний
for(m=0;m<n;m++)
  {for(i=0;i<n;i++)
   {for(j=0;j<n;j++)
     {if(i!=j) //меняем только те числа, которые находятся не на главной диагонали
      if(mat[i][j]!=0) //нули, стоящие не на главной диагонали я принимала за бесконечность, согласно алгоритму Флойда
       mat[i][j]=min(mat[i][j],mat[i][m]+mat[m][j]);
      else mat[i][j]=mat[i][m]+mat[m][i];
      }
   }
  }
//вывод матрицы расстояний
for(i=0;i<n;i++)
 {for(j=0;j<n;j++)
       cout<<mat[i][j]<<" ";
       cout<<endl;
 }
 
delete[] mat;
getch();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.02.2011, 23:18     МАТРИЦА РАССТОЯНИЙ ГРАФА
Посмотрите здесь:

Матрица расстояний для невзвешенного графа - C++
Нужно найти радиус, диаметр, центр неориентированного невзвешенного графа Для этого, как я поняла, нужна матрица расстояний. Как её...

Поиск самых коротких расстояний между любыми двумя вершинами графа по методу Шимбела - C++
у меня большие проблемы с логикой программирования) поэтому обращаюсь к вам за помощью..... Поиск самых коротких расстояний между любыми...

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

Матрица/связные_списки смежности для ориентированного графа - C++
Скажите, пожалуйста, когда я создаю матрицу смежности для ориентированного графа, то в матрице у меня должны присутствовать только 0 и 1?...

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

Перевода расстояний в дюймах в сантиметры - C++
таблицу перевода расстояний в дюймах в сантиметры для значений 2, 4, 6, ..., 12 дюймов (1 дюйм = 25.4 мм);

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
16.02.2011, 23:37     МАТРИЦА РАССТОЯНИЙ ГРАФА #2
вот подробный алгоритм Флойда-Уоршелла
asics
Freelance
Эксперт С++
2846 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
16.02.2011, 23:43     МАТРИЦА РАССТОЯНИЙ ГРАФА #3
Еще тут что-то есть.
dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
16.02.2011, 23:45     МАТРИЦА РАССТОЯНИЙ ГРАФА #4
для образовательных целей и любопытства можно посмотреть визуализатор алгоритма
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2011, 10:55     МАТРИЦА РАССТОЯНИЙ ГРАФА
Еще ссылки по теме:

Перевод расстояний из дюймов в сантиметры - C++
1. Напишите программу печати таблицы перевода расстояний из дюймов в сантиметры для значений длин от 1 до 20 дюймов. 1 дюйм = 2,54 см. (1...

Вывести таблицу расстояний между городами - C++
в принципе я знаю алгоритм решения ее)) но я не смог перенести свой алгоритм на c++)) вот сама задача: заданы 7 городов ...

Таблица перевода расстояний из км в морские мили - C++
Напечатать таблицу перевода расстояний из км в морские мили для значений от 1 до 10 км с шагом 1 км (1 м. миля=1,825 км)

Реализация алгоритма А* (поиск кратчайших расстояний на графе) - C++
В общем, уже несколько дней бьюсь над небольшой проблемой: написал поиск кратчайших путей на графе на основе алгоритма А*. Пути...

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

АТД Графы. Поиск суммы расстояний между городами. - C++
Здравствуйте! Нужна помощь! Всем известная задача и в сети конечно много разнообразных тем! но не одна из них не доведена до...


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

Или воспользуйтесь поиском по форуму:
nikalerka
0 / 0 / 0
Регистрация: 21.11.2010
Сообщений: 77
17.02.2011, 10:55  [ТС]     МАТРИЦА РАССТОЯНИЙ ГРАФА #5
большое спасибо за ссылки.
а конкретно по тому что я написала мне может кто-нибудь что-нибудь сказать??
Yandex
Объявления
17.02.2011, 10:55     МАТРИЦА РАССТОЯНИЙ ГРАФА
Ответ Создать тему
Опции темы

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