A good algorithm
Any one here know a good algorithm to find the shortest
loop in a graph?
Re: A good algorithm
kheo thi N^3, con khong thi khoang N^4 !
Tong Hop Vo Dich @
QH@
ENGLISH, please. (Was: A good algorithm)
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
Re: A good algorithm
Posted by
HNT 12 Jun 2001 08:37
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?
Re: A good algorithm
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?
Re: A good algorithm
wHY DON'T YOU EXPLAIN THAT ALGORITHM.
iN VIETNAMESE IT'S "QUY HOACH DONG"???
Re: ENGLISH, please. (Was: A good algorithm) <= sometime i wanna use my mother languague, ok ;) ?
> 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
Re: A good algorithm <= this one, is not "KHEO" (O(N^4))
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@
Re: A good algorithm <= this one, is not
> 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!
