Re: [理工] [DS] Dijkstra Algorithm

[genius945 (添財)]

※ 引述《jim055006 (jim)》之銘言：
: Dijkstra Algo 不能有負邊存在
: ex:
:         A
:        / \
:     3 /   \ 2       由A出發
:      /     \
:     B-------C
:        -2
:   S    u    D[B]  D[C]
: -------------------------
: {A}    -      3     2
  {AC}   C      0     |
  {ACB}  B      |     |


d(A,C)=2

但A到C的最短距離應為3+(-2)=1
不為2

因此有負邊存在,Dijkstra algo可能無法正確地運作


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.27.227.55
→ jim055006:太感謝G大了.....我了解了...