4.4.1 - Dijkstra's algorithm

• 不可有負邊存在

1. 演算法

Cost Matrix C[i][j]:為一個nxn矩陣，n=|V|

$C[i,j]= \begin{cases} 邊長, & \textrm{if (i, j) exists}\\ ∞, & \textrm{if (i, j) doesn't exist}\\ 0, & \textrm{if i = j} \end{cases}$

$S[i]= \begin{cases} 0, & \textrm{未確定起點到i的shortest path length}\\ 1, & \textrm{已確定起點到i的shortest path length} \end{cases}$

$Dist[i]:\textrm{起點到i的shortest path length}$

$Dist[w]=min\{Dist[w],\ Dist[u]+C[u,w]\}$

2. 範例

求5到各點的最短路徑？