Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.94/50: Рейтинг темы: голосов - 50, средняя оценка - 4.94
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
1

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

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

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

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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.04.2013, 10:38
Ответы с готовыми решениями:

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

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

Как найти НЕ Кратчайший путь в графе ?
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан...

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

23
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
29.04.2013, 14:56 2
алгоритм Флойда с рекурсией...?)
0
670 / 198 / 29
Регистрация: 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;
    }
}
Этот алгоритм используется для нахождения всех кратчайших путей в графе (между любой парой вершин)
0
212 / 214 / 44
Регистрация: 20.12.2011
Сообщений: 635
29.04.2013, 16:05 4
Цитата Сообщение от Ternsip Посмотреть сообщение
Этот алгоритм используется для нахождения всех кратчайших путей в графе (между любой парой вершин)
у ТС вопрос был не в нахождении кратчайшего пути(он его уже нашёл этим алгоритмом), а в том, что ему необходимо использовать рекурсию для нахождения этого пути.

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

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

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

Препод сказал функция должна принимать саму матрицу .пройденное расстояние .количество сделанных шагов и текущую координату(город)
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
29.04.2013, 17:49 9
вы так и не прояснили: вам нужно узнать расстояние между какими-то двумя конкретными городами или для всех пар?
0
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 17:50  [ТС] 10
Цитата Сообщение от salam Посмотреть сообщение
вы так и не прояснили: вам нужно узнать расстояние между какими-то двумя конкретными городами или для всех пар?
между двумя конкретными.
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
29.04.2013, 17:51 11
начнем тогда с того, что алгоритм Флойда-Уоршелла к этой задаче применять нерационально.
0
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 17:52  [ТС] 12
да это я уже понял...я сначала находил для всех а потом уже в зависимости какой путь интересен пользователю выдавал результат.
0
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 17:54 13
LEBRON32RUS,
Цитата Сообщение от LEBRON32RUS Посмотреть сообщение
Препод сказал функция должна принимать саму матрицу .пройденное расстояние .количество сделанных шагов и текущую координату(город)
Ужас, если рекурсия будет принимать каждый раз матрицу(не по ссылке), то у вас будет Memory limit, т.к. очень много займёт памяти. Наверное вам без рекурсии надо. Позвольте мне угодать, вы хотите сделать функцию кратчайшего расстояния между двумя вершинами, в аргументы которой будет подаваться матрица смежности графа.
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
29.04.2013, 17:54 14
тогда напишите Дейкстру, сравните время работы с рекурсией и без и задайте преподавателю вопрос, который витает в воздухе...)
0
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 17:56  [ТС] 15
Я говорил преподу что рекурсией нерационально а он уперся и говорит. "Задание на рекурсию"
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
29.04.2013, 17:58 16
да понятно, извините за болтовню.
Дейкстру писать умеете?
0
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:01  [ТС] 17
Цитата Сообщение от salam Посмотреть сообщение
да понятно, извините за болтовню.
Дейкстру писать умеете?
Научусь.но что мне даст Дейкстра?там есть рекурсия?
0
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 18:01 18
LEBRON32RUS, да, переделайте же вы цикл в рекурсию, омфг...
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
29.04.2013, 18:02 19
Цитата Сообщение от LEBRON32RUS Посмотреть сообщение
Научусь.но что мне даст Дейкстра?там есть рекурсия?
там ее нет, потому что она неэффективна. там есть цикл. а в информатике есть теорема о взаимозаменяемости цикла и рекурсии. изучайте.
0
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
29.04.2013, 18:05  [ТС] 20
Цитата Сообщение от salam Посмотреть сообщение
там ее нет, потому что она неэффективна. там есть цикл. а в информатике есть теорема о взаимозаменяемости цикла и рекурсии. изучайте.
а в Флойде это можно сделать?Просто Дейкстра обьемный а этот короче.
0
29.04.2013, 18:05
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.04.2013, 18:05
Помогаю со студенческими работами здесь

Найти кратчайший путь
Добрый день, знаю таких программ куча и т.д., но найти подходящую я не смог. Может у кого имеется в...

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru