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

Кратчайший путь в графе(Рекурсия) - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.73
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 10:38     Кратчайший путь в графе(Рекурсия) #1
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без рекурсии. Помогите изменить прогу под исполььзование рекурсии

input.txt

0 500 3 500 500
500 0 9 500 4
3 9 0 3 8
500 500 3 0 2
500 4 8 2 0

500-прямой дороги нет

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
#include <iostream>
#include <stdio.h>
 
using namespace std;
int main()
{
 
 
 
   int i, j,n,k, A[5][5]; 
   FILE *fp; 
   ///Матрица из файла
   fp = fopen("input.txt", "r"); 
   for ( i = 0; i < 5; i ++ )      
     for ( j = 0; j < 5; j ++ )   
       if ( 0 == fscanf(fp,"%d",&A[i][j]) ) 
           { 
           puts("Не хватает памяти"); 
           fclose ( fp );  
           return 1;        
           } 
   fclose ( fp );
   
   
    
   for (i = 0; i < 5; i++) 
    for (j = 0; j < 5; j++)
        for (k = 0; k < 5; k++)
            if (A[j][k] > A[j][i] + A[i][k])
             
             {
        
                 A[j][k] = A[j][i] + A[i][k];
             }
            
             
for (i = 0; i <5 ; i++) 
{
for (j = 0; j <5 ; j++)        
{
   printf("%d ",A[i][j]);
}
printf("\n");
}
system("pause");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 18:06     Кратчайший путь в графе(Рекурсия) #21
LEBRON32RUS,
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
#include <iostream>
#include <set>
#include <vector>
#include <limits>
#include <queue>
#include <string>
#include <map>
#include <ctime>  
#include <stack>
 
using namespace std;
 
int tmp,n,a[102][102],inf = 100000000;
 
void frn_0(int k, int i, int j) {
    if (j >= n) {
        i++;
        j = 0;
    }
    if (i >= n) {
        k++;
        i = 0;
    }
    if (k >= n)
        return;
    a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
    frn_0(k, i, j+1); 
}
 
int main(){            
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    cin >> n;
    for (int i = 0; i< n; i++)
        for (int j = 0; j < n; j++){
            cin >> tmp;
            a[i][j] = (tmp == 0)? inf : tmp;
        }
    frn_0(0, 0, 0);
    for (int i = 0; i< n; i++){
        for (int j = 0; j < n; j++)
            cout<<((a[i][j]<inf)? a[i][j] : 0)<<" ";
        cout<<endl;
    }
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:19  [ТС]     Кратчайший путь в графе(Рекурсия) #22
у меня этот код компилируется но не работает...пытаюсь ввести n а он закрывается
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
29.04.2013, 18:20     Кратчайший путь в графе(Рекурсия) #23
фриопэн закомментите...)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2013, 18:27     Кратчайший путь в графе(Рекурсия)
Еще ссылки по теме:

C++ Найти кратчайший путь из вершины u в вершину v
Как найти кратчайший путь в лабиринте? C++
C++ Как найти НЕ Кратчайший путь в графе ?

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

Или воспользуйтесь поиском по форуму:
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:27  [ТС]     Кратчайший путь в графе(Рекурсия) #24
Цитата Сообщение от salam Посмотреть сообщение
фриопэн закомментите...)
было бы неплохо.я вообще не понимаю как он передает данные из файла в массив и передает ли вообще
Yandex
Объявления
29.04.2013, 18:27     Кратчайший путь в графе(Рекурсия)
Ответ Создать тему
Опции темы

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