Any one here know a good algorithm to find the shortest
loop in a graph?

kheo thi N^3, con khong thi khoang N^4 !

Tong Hop Vo Dich @

QH@

Don't you understand, what "Write in English, please."
means? Even if you knew him personally, it would be
more friendly to the rest of us if you followed this
advice. It's kind of annoying not to understand people
talk.

Best regards,
Stefan Pochmann

Mmmm, I think that you shouldn't know it ( N^3 Dynamic
Programming)
> Any one here know a good algorithm to find the shortest
> loop in a graph?

u CO THE NOI RO VE THUAT TOAN O.
TUI CHI NGHI RA 2 CACH:
-DUNG LOANG CHI TUNG CAP DINH
-DUNG LOANG DE TIM CHU TRINH
tUI KHONG BIET CACH THU 2 CO DUNG O?

wHY DON'T YOU EXPLAIN THAT ALGORITHM.
iN VIETNAMESE IT'S "QUY HOACH DONG"???

> Don't you understand, what "Write in English, please."
> means? Even if you knew him personally, it would be
> more friendly to the rest of us if you followed this
> advice. It's kind of annoying not to understand people
> talk.
>
> Best regards,
> Stefan Pochmann

choose one node for the first city i, the "remove" it from
the list, now, you find the shortest path between each pairs
of the remaining nodes, (using floyd algorithm with O(N^3))
for each d(u, v) (u <> v), compare the sum A[i][u] + d[u][v]
+ A[v][i] with the best root

There's some tricky that, with each route, you can "convert"
it the another route, which is better for programming,
satisfy that the first city is the lowest number => when try
to find the shortest way like the algorithm above, u and v
always > i !

Good luck !

QH@

> choose one node for the first city i, the "remove" it
from
> the list, now, you find the shortest path between each
pairs
> of the remaining nodes, (using floyd algorithm with O
(N^3))
> for each d(u, v) (u <> v), compare the sum A[i][u] + d[u]
[v]
> + A[v][i] with the best root
>
> There's some tricky that, with each route, you
can "convert"
> it the another route, which is better for programming,
> satisfy that the first city is the lowest number => when
try
> to find the shortest way like the algorithm above, u and
v
> always > i !
>
> Good luck !
>
> QH@
But why  O (N^3) ????
 Floyd's algorithm ( O(N^3)  ) will be used several
( O(N) ) times!