Ещё графовый алгоритм

← →
asdqwer (2004-01-05 11:26) [0]

Нужно найти в ориентированном графе (т.е. со стрелочками :-) такую вершину, у которой глубина дерева минимальна или можно эту самую глубину. Я имею ввиду, что из той вершины можно будет "обойти" весь граф быстрее всего, думаю это понятно. Заранее спасибо.

← →
Ega23 © (2004-01-05 11:28) [1]

Ту не в Дубне, случайно, учишься?

← →
pasha_golub © (2004-01-05 11:52) [2]

Разновидность алгоритма Дейкстры нахождения кратчайнего пути, назывется, если я конечно не ошибаюсь, алгоритм Уоршела. Сложность О(n^3). Это просто алгоритм Дейкстры примененный по очереди ко всем узлам графа. Ориентированный или нет - это не важно. Надо будет составить только таблицу инцидентности

← →
Romkin © (2004-01-05 11:55) [3]

По-моему, алгоритм Дейкстры для ориентированных графов не работает... Или наоборот?

← →
JibSkeart © (2004-01-05 12:14) [4]

2 Romkin
ориентированый граф грубо говоря который имеет напровление , так если помню еще :) ,
а у меня задача такая стояла и я ее реализовал именно через
алгоритм Дейкстры нахождения кратчайнего пути ...

Может снчала нужно определиться: ориентированый граф или дерево?
Для дерева - обычная задача балансировки.

2Romkin
Алгоритм Дейкстры работает с таблицей (матрицей) инцидентности, емцу накакать на ориентированность, просто матрица будет не симметрична. :-)

2JibSkeart
Ориентированный граф, это у которого связи имеют направление, но не всегда однонаправленное. Представим себе ситуайию. Из города А в город В построена новейшая магистраль в три полосы, а из города В в город А идет маленькая узенькая дорога. Так вот связь тут двухсторонняя, но пропускаемость разная. Такого рода велечины назыают весом связи (или узла в зависимости от задачи). И тогда встают задачи о взвешенных графах. Так вот ориентированный граф - это частный случай взвешенного графа.

2DAC
Дерево - частный случай графа и не более.

Ещё графовый алгоритм Найти похожие ветки