Форум программистов, компьютерный форум 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");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
29.04.2013, 14:56     Кратчайший путь в графе(Рекурсия) #2
алгоритм Флойда с рекурсией...?)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 15:56     Кратчайший путь в графе(Рекурсия) #3
LEBRON32RUS, Классический алгоритм Флойда-Уоршелла пишется в 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
#include <iostream>
using namespace std;
 
int tmp,n,a[102][102],inf = 100000000;
 
void main(void){
    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;
        }
    for (int k = 0; k < n; k++)
        for (int i = 0; i< n; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
    
    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;
    }
}
Этот алгоритм используется для нахождения всех кратчайших путей в графе (между любой парой вершин)
Fler
207 / 209 / 9
Регистрация: 20.12.2011
Сообщений: 635
29.04.2013, 16:05     Кратчайший путь в графе(Рекурсия) #4
Цитата Сообщение от Ternsip Посмотреть сообщение
Этот алгоритм используется для нахождения всех кратчайших путей в графе (между любой парой вершин)
у ТС вопрос был не в нахождении кратчайшего пути(он его уже нашёл этим алгоритмом), а в том, что ему необходимо использовать рекурсию для нахождения этого пути.

смотрите в сторону обхода графа в глубину или ширину
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 16:12     Кратчайший путь в графе(Рекурсия) #5
Fler, через dfs(Обход в глубину) никогда не стоит искать кратчайшее расстояние! Подчёркиваю.
bfs(обход в глубину) в классической реализации -- очередь с циклом.
Но обычный цикл всегда можно переделать в рекурсию, что ухудшит производительность.
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 16:21  [ТС]     Кратчайший путь в графе(Рекурсия) #6
ну может кто нибудь сможет показать эту функцию рекурсивную(пожалуйста)

Добавлено через 1 минуту
Цитата Сообщение от salam Посмотреть сообщение
алгоритм Флойда с рекурсией...?)
Нет не алгоритм флойда с рекурсией а новый метод какой нибудь.подразумевающий использование рекурсии и решающий мою задачу
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 16:30     Кратчайший путь в графе(Рекурсия) #7
LEBRON32RUS, http://habrahabr.ru/post/162915/ вот алгоритм поиска кратчайшего пути JPS очень шустро работает. Там рекурсивная функция прыжка. Но он не ко всем графам применим, а если точнее, то очень не ко многим. Например, к прямоугольным лабиринтам
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 17:42  [ТС]     Кратчайший путь в графе(Рекурсия) #8
что то совсем туго я понимаю то что там разбирается.
вот условие задачи.мало ли может я с этими графами совсем нетуда пошел может и по другому эта задача решается

Дана матрица размером NxN с расстояниями между городами при наличии прямой дороги между ними. По вертикали содержаться города откуда выезжаем, по горизонтали – куда. На пересечении - расстояние по прямой дороге. Если прямой дороги нет, в соответствующем элементе матрицы записывается число “-1”. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги.

Препод сказал функция должна принимать саму матрицу .пройденное расстояние .количество сделанных шагов и текущую координату(город)
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
29.04.2013, 17:49     Кратчайший путь в графе(Рекурсия) #9
вы так и не прояснили: вам нужно узнать расстояние между какими-то двумя конкретными городами или для всех пар?
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 17:50  [ТС]     Кратчайший путь в графе(Рекурсия) #10
Цитата Сообщение от salam Посмотреть сообщение
вы так и не прояснили: вам нужно узнать расстояние между какими-то двумя конкретными городами или для всех пар?
между двумя конкретными.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
29.04.2013, 17:51     Кратчайший путь в графе(Рекурсия) #11
начнем тогда с того, что алгоритм Флойда-Уоршелла к этой задаче применять нерационально.
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 17:52  [ТС]     Кратчайший путь в графе(Рекурсия) #12
да это я уже понял...я сначала находил для всех а потом уже в зависимости какой путь интересен пользователю выдавал результат.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 17:54     Кратчайший путь в графе(Рекурсия) #13
LEBRON32RUS,
Цитата Сообщение от LEBRON32RUS Посмотреть сообщение
Препод сказал функция должна принимать саму матрицу .пройденное расстояние .количество сделанных шагов и текущую координату(город)
Ужас, если рекурсия будет принимать каждый раз матрицу(не по ссылке), то у вас будет Memory limit, т.к. очень много займёт памяти. Наверное вам без рекурсии надо. Позвольте мне угодать, вы хотите сделать функцию кратчайшего расстояния между двумя вершинами, в аргументы которой будет подаваться матрица смежности графа.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
29.04.2013, 17:54     Кратчайший путь в графе(Рекурсия) #14
тогда напишите Дейкстру, сравните время работы с рекурсией и без и задайте преподавателю вопрос, который витает в воздухе...)
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 17:56  [ТС]     Кратчайший путь в графе(Рекурсия) #15
Я говорил преподу что рекурсией нерационально а он уперся и говорит. "Задание на рекурсию"
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
29.04.2013, 17:58     Кратчайший путь в графе(Рекурсия) #16
да понятно, извините за болтовню.
Дейкстру писать умеете?
LEBRON32RUS
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:01  [ТС]     Кратчайший путь в графе(Рекурсия) #17
Цитата Сообщение от salam Посмотреть сообщение
да понятно, извините за болтовню.
Дейкстру писать умеете?
Научусь.но что мне даст Дейкстра?там есть рекурсия?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 18:01     Кратчайший путь в графе(Рекурсия) #18
LEBRON32RUS, да, переделайте же вы цикл в рекурсию, омфг...
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
29.04.2013, 18:02     Кратчайший путь в графе(Рекурсия) #19
Цитата Сообщение от LEBRON32RUS Посмотреть сообщение
Научусь.но что мне даст Дейкстра?там есть рекурсия?
там ее нет, потому что она неэффективна. там есть цикл. а в информатике есть теорема о взаимозаменяемости цикла и рекурсии. изучайте.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2013, 18:05     Кратчайший путь в графе(Рекурсия)
Еще ссылки по теме:

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

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

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

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