Правила форума
Теория Графов. Метод Шимбелла., озадачился...
| М | Задача явно не по теории Паскаля, как я понимаю. Переношу в Алгоритмы. Lapp |
На курсовую мне попалась тема Теория Графов, Метод Шимбелла.
По неё мне нужно написать немного теории и сделать программу.
Теории по самим Графам нашёл кучу, а конкретно по методу Шимбелла -
почти ничего
На этом форуме тоже ничего об этом не нашёл.И вот думаю... может быть есть название, идентичное Методу Шимбелла?
В интернете кое-что сумел найти, но это слишком мало...
Подскажите, пожайлуста, где можно об этом найти поподробнее
и желательно с кусочками кода программы...
Вот что я нашёл в интернете:
Цитата
Алгоритм Шимбелла находит кратчайшие расстояния между всеми парами
вершин.
Матрица смежности для алгоритма Шимбелла строится по следующим
правилам: -
¦ весу ребра {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
После завершения работы алгоритма в матрице С остаются кратчайшие
расстояния.
вершин.
Матрица смежности для алгоритма Шимбелла строится по следующим
правилам: -
¦ весу ребра {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 -
