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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.73
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
#1

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

29.04.2013, 10:38. Просмотров 3239. Ответов 23
Метки нет (Все метки)

Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без рекурсии. Помогите изменить прогу под исполььзование рекурсии

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");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2013, 10:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Кратчайший путь в графе(Рекурсия) (C++):

Кратчайший путь в графе. - C++
Такая задача: Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь из вершины s в вершину t. ...

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

Как найти НЕ Кратчайший путь в графе ? - C++
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа: 5 1 1 2 3...

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

Кратчайший путь коня с++ - C++
помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б

Найти кратчайший путь из вершины u в вершину v - C++
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

23
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 748
29.04.2013, 17:58 #16
да понятно, извините за болтовню.
Дейкстру писать умеете?
0
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:01  [ТС] #17
Цитата Сообщение от salam Посмотреть сообщение
да понятно, извините за болтовню.
Дейкстру писать умеете?
Научусь.но что мне даст Дейкстра?там есть рекурсия?
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 18:01 #18
LEBRON32RUS, да, переделайте же вы цикл в рекурсию, омфг...
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 748
29.04.2013, 18:02 #19
Цитата Сообщение от LEBRON32RUS Посмотреть сообщение
Научусь.но что мне даст Дейкстра?там есть рекурсия?
там ее нет, потому что она неэффективна. там есть цикл. а в информатике есть теорема о взаимозаменяемости цикла и рекурсии. изучайте.
0
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:05  [ТС] #20
Цитата Сообщение от salam Посмотреть сообщение
там ее нет, потому что она неэффективна. там есть цикл. а в информатике есть теорема о взаимозаменяемости цикла и рекурсии. изучайте.
а в Флойде это можно сделать?Просто Дейкстра обьемный а этот короче.
0
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;
}
0
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:19  [ТС] #22
у меня этот код компилируется но не работает...пытаюсь ввести n а он закрывается
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 748
29.04.2013, 18:20 #23
фриопэн закомментите...)
0
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:27  [ТС] #24
Цитата Сообщение от salam Посмотреть сообщение
фриопэн закомментите...)
было бы неплохо.я вообще не понимаю как он передает данные из файла в массив и передает ли вообще
0
29.04.2013, 18:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2013, 18:27
Привет! Вот еще темы с ответами:

Как найти кратчайший путь в лабиринте? - C++
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить. ...

Найти кратчайший путь шахматного короля - C++
Здравствуйте, имеется задача: Есть шахматное поле NxM N, M ≤ 10^9 На шахматном поле отмечено два прямоугольника размерами не менее...

Найти самый кратчайший путь в массиве - C++
У меня есть динамический массив в котором количество строк задаётся при выполнении программы, а количество строк неизменно и равно 3. Мне...

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


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

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

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