IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Теория Графов. Метод Шимбелла., озадачился...
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 1
Пол: Мужской
Реальное имя: Николай

Репутация: -  0  +


М
Задача явно не по теории Паскаля, как я понимаю. Переношу в Алгоритмы. Lapp



На курсовую мне попалась тема Теория Графов, Метод Шимбелла.
По неё мне нужно написать немного теории и сделать программу.
Теории по самим Графам нашёл кучу, а конкретно по методу Шимбелла -
почти ничего unsure.gif На этом форуме тоже ничего об этом не нашёл.
И вот думаю... может быть есть название, идентичное Методу Шимбелла?
В интернете кое-что сумел найти, но это слишком мало...
Подскажите, пожайлуста, где можно об этом найти поподробнее
и желательно с кусочками кода программы...

Вот что я нашёл в интернете:
Цитата
Алгоритм Шимбелла находит кратчайшие расстояния между всеми парами
вершин.

Матрица смежности для алгоритма Шимбелла строится по следующим
правилам: -
¦ весу ребра {i,j} , если ребро существует
A =¦0, если i=j
i,j ¦#, иначе
L
Матрица кратчайших расстояний находится по следующемуалгоритму:

С=А

Для i от1 до N
Для j от1 до N
N
С[i,j]=min{С +С }
k=1 i,k j,k
Для i от N до1
Для j от N до1
N
С[i,j]=min{С +С }
k=1 i,k j,k

После завершения работы алгоритма в матрице С остаются кратчайшие
расстояния.


Сообщение отредактировано: Lapp -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


В любом случае, ничего лучше, чем алгоритм Флойда, ты, скорее всего, не найдешь. Скорее всего он то тебе и нужен. То что ты запостил на него похоже, только индексы съехали куда-то smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Видимо ты взял это отсюда:
Алгоритм Шимбелла

Я посмотрел - там есть и Флойд и Шимбелл, выходит это не одно и то-же (если автор не дилетант)
но алгоритм, который там описан:
Код
С=А                                                                
                                                                              
           Для i от 1 до N                                                    
             Для j от 1 до N                                                  
                       N                                                      
               С[i,j]=min{С   +С   }                                          
                      k=1  i,k  j,k                                            
           Для i от N до 1                                                    
             Для j от N до 1                                                  
                       N                                                      
               С[i,j]=min{С   +С   }                                          
                      k=1  i,k  j,k  

Конечно полный бред и по каким правилам он написан - не понятно.
Я думаю тебе стоит поговорить с преподавателем и сменить тему на алгоритм Флойда или попросить его разъяснить этот алгоритм (я сомневаюсь, что он даст что-то отличное от Флойда).


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Уважаемый КашаК,

Я столкнулась с той же проблемой, а именно: курсовая по теме "Поиск кратчайшего пути в графах. Метод Шимбелла". Можно ли узнать, как (в далеком 2007) вы ее решили?
ПС: тему уже не поменять.

Заранее спасибо!
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Гость @ 16.03.2011 12:14) *
Уважаемый КашаК,

Уважаемый Гость!

1. На форуме принято обращаться ко всем, а если хочешь что-то сказать кому-то лично - пиши в личном сообщении.
2. Немного странно ожидать ответа от человека, запостившего одно сообщение и даже не ответившего на ответные посты, а также не заходившего на форум с мая 2007г. Как, по-твоему, он прочтет этот твой призыв? Проинтуичит?.. бросится к компьютеру, вспомнит адрес форума, вспомнит свой пароль - и в приступе филантропии скажет тебе заветное решение?.. blink.gif

ой, не смеши..

Если хочешь нормальной деловой беседы - регистрируйся и говори со всеми.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Цитата(Lapp @ 16.03.2011 12:28) *

Уважаемый Гость!


Ну отчего вы так сразу набросились на бедную девушку) sad.gif
Просто надеялась, кто-нибудь поможет, а оказалось, кроме возмущения ничего дельного не предложите)
Бывают такие безвыходные ситуации, что порой надеешься на любую помощь, даже от человека, который так давно не заходил в онлайн !help.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Гость @ 20.03.2011 19:14) *
Ну отчего вы так сразу набросились на бедную девушку) sad.gif
Просто надеялась, кто-нибудь поможет, а оказалось, кроме возмущения ничего дельного не предложите)
Бывают такие безвыходные ситуации, что порой надеешься на любую помощь, даже от человека, который так давно не заходил в онлайн !help.gif

Милая бедная девушка!
Я прекрасно понимаю, что "бывают такие ситуации". И никто на особо не набрасывался, я просто удивился и попробовал показать тебе реальность.
Ты можешь продолжать надеятся на чудо - только, чесслово, лучше уж тогда пойди купи лотерейный билет, потому что вероятность того, что ты выиграешь сумму, которая обеспечит тебе безбедное существование на всю оставшуюся жизнь и сделает ненужными всякие там мелочи типа курсовых, ЗНАЧИТЕЛЬНО ВЫШЕ, чем что КашаК заглянет сюда и поможет yes2.gif.

А еще ты можешь поступить так, как я написал в конце предыдущего поста. Ничего не гарантирую, но помочь постараемся.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Перефразируйте пожалуйста
Завидую тем, кто досмотрел до конца.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Профи
****

Группа: Пользователи
Сообщений: 652
Пол: Мужской
Реальное имя: Алексей

Репутация: -  20  +


Зарегистрируйся ,создай тему,подними интересующий тебя попрос и тебе постараются дать на него ответ.
Лично я заглянув в поиск увидел
Где то в серединке.
И на закуску.
Все детално и с примерами описанно и написано,что надо реализовать.

Сообщение отредактировано: Krjuger -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 20.02.2018 9:06
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"