申論題 - 阿摩線上測驗

申論題資訊

試卷：111年 - 111-1 國立竹北高中教師甄選試題：資訊科技科#107622
科目：教甄◆資訊科技概論專業(電腦科)
年份：111年
排序：0

申論題內容

1. Floyd-Warshall 是一種用來計算圖中所有點對最短路徑長的演算法。假設圖中共有 V 個點、E 個邊，其原理為宣告一個二維陣列 d[V][V]，以 d[i][j]表示點 i 至點 j 的最短路徑長。過程中若對於中途點 k，符合 d[i][j] ＞ d[i][k] + d[k][j] 則更新 d[i][j] 數值。請問此演算法時間複雜度為何？

詳解 (共 2 筆)

詳解提供者：sheehan

O(V³)

詳解提供者：hn.hsiao