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

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

16.02.2011, 23:18. Просмотров 4378. Ответов 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();
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.02.2011, 23:18
Ответы с готовыми решениями:

Матрица расстояний для невзвешенного графа
Нужно найти радиус, диаметр, центр неориентированного невзвешенного графа Для...

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

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

Матрица смежности графа - поиск в глубину
Здравствуйте дорогие форумчане. У меня тут небольшая ошибка. Никак не могу...

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

4
dxdy
97 / 97 / 14
Регистрация: 14.06.2010
Сообщений: 284
16.02.2011, 23:37 2
вот подробный алгоритм Флойда-Уоршелла
0
asics
Freelance
Эксперт С++
2854 / 1789 / 355
Регистрация: 09.09.2010
Сообщений: 3,841
16.02.2011, 23:43 3
Еще тут что-то есть.
0
dxdy
97 / 97 / 14
Регистрация: 14.06.2010
Сообщений: 284
16.02.2011, 23:45 4
для образовательных целей и любопытства можно посмотреть визуализатор алгоритма
0
nikalerka
0 / 0 / 0
Регистрация: 21.11.2010
Сообщений: 77
17.02.2011, 10:55  [ТС] 5
большое спасибо за ссылки.
а конкретно по тому что я написала мне может кто-нибудь что-нибудь сказать??
0
17.02.2011, 10:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2011, 10:55

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

По заданной матрице смежности простого графа построить каркас этого графа с использованием поиска в ширину
Задание: заданно матрицу смежности простого графа. Построить каркас этого...

дана квадратичная матрица z[n][n]. составить программу, которая если матрица симметричная(транспонированная матрица равна исходной), сделает ее не сим
помогите пожалуйста. условие: дана квадратичная матрица z. составить...


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

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

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