Алгоритм, может кто-нибудь подобное решал...

← →
Cossys (2002-02-12 10:34) [3]

to Ura

Это задача из теории графов.

to Builder

В общем задача следующая. Есть матрица В с m солбцами (в столбцах отражаются дуги) и n строками (в строках отображаются вершины графа). Самый простенький пример (х1 - начало, х3 -конец):
x2 x3
0-----0
|\ |
| \ |
| \ |
| \ |
0-----0
x1 x4

Для такого графа матрица В записывается (1 - начало дуги, -1 - конец, 0 - не соприкосаются):
1 2 3 4 5
- - - - -
1| 1 0 1 0 0
В= 2|-1 1 0 0 1
3| 0-1 0-1 0
4| 0 0-1 1-1

Фактически, матрица В - закодированая структура орграфа. Если задана матрица U={u1,...,u5} - весы дуг (другими словами - стоимость перевозки от, допустим, х1 до х2). МАТРИЦЫ ЕСТЬ... ЧТО ДЕЛАТЬ ДАЛЬШЕ??? Очевидно, как-то эти матрицы надо перемножить.

Нужны Ваши знания

Алгоритм, может кто-нибудь подобное решал... Найти похожие ветки