|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
06.12.2007, 03:53 | #1 |
Регистрация: 09.11.2007
Сообщений: 9
|
Алгоритм Флойда. Поиск Кратчайшего пути.
Вообщем мне нужна реализация алгоритма Флойда по поиску кратчайшего пути между точками графа на Delphi. Так же нужна инфа по самому этому алгоритму, если у кого-то есть хоть что-нить, либо знает где найти пишите. Заренее спасибо.
P.S. Курсяк мой горит) Аж сминим пламенем) |
06.12.2007, 06:12 | #2 |
C# developer
Форумчанин
Регистрация: 03.10.2007
Сообщений: 393
|
Дано: непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кpатчайших пyтей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.
Инициализация: 1. Построим матрицу D0 размерности |V| x |V|, элементы которой определяются по правилу: dii0= 0; dij0= Weight(vi, vj), где i<>j, если в графе существует ребро (дуга) (vi, vj); dij0= бесконечность , где i<>j, если нет ребра (дуги) (vi, vj). 2. m:=0. Основная часть: 1. Построим матрицу Dm+1 по Dm, вычисляя ее элементы следующим образом: dijm+1=min{dijm, di(m+1)m + d(m+1)jm}, где i<>j; diim+1=0 (*). Если dimm + dmim < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину vi; ВЫХОД. 2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D|V| равны длинам кратчайших путей между соответствующими вершинами; ВЫХОД. Если требует найти сами пути, то перед началом работы алгоритма построим матрицу P с начальными значениями элементов pij=i. Каждый раз, когда на шаге (1) значение dijm+1 будет уменьшаться в соответствии с (*) (т.е. когда di(m+1)m + d(m+1)jm<dijm), выполним присваивание pij:=p(m+1)j. В конце работы алгоритма матрица P будетопределять кратчайшие пути между всеми парами вершин: значение pij будет равно номеру предпоследней вершины в пути между i и j (либо pij=i, если путь не существует). Примечаниe: если граф - неориентированный, то все матрицы Dm являются симметричными, поэтому достаточно вычислять элементы, находящиеся только выше (либо только ниже) главной диагонали. Если не поможет тогда вот:
I like WPF
Последний раз редактировалось kommunist; 06.12.2007 в 06:20. |
06.12.2007, 19:59 | #3 |
Регистрация: 09.11.2007
Сообщений: 9
|
Прога работать отказывается. Ругается на что-то.
|
07.12.2007, 12:52 | #4 |
C# developer
Форумчанин
Регистрация: 03.10.2007
Сообщений: 393
|
Код:
I like WPF
|
10.04.2011, 19:43 | #5 |
Новичок
Джуниор
Регистрация: 09.04.2011
Сообщений: 1
|
http://kontrolnaya-rabota.ru/s/kalkulyator/-сайт решает всё по математике
|
06.10.2014, 18:29 | #6 |
Новичок
Джуниор
Регистрация: 06.10.2014
Сообщений: 1
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск пути в лабиринте - Пролог | yulia | Помощь студентам | 15 | 21.08.2010 00:14 |
Пути к данным | Лубышев | Общие вопросы Delphi | 3 | 21.01.2008 18:56 |
Системные пути | Lonix | Общие вопросы Delphi | 8 | 14.09.2007 17:10 |