戴克斯特拉算法（英語：Dijkstra"s algorithm）是由荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾·戴克斯特拉提出。迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖的單源最短路徑問題，算法最終得到一個(gè)最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個(gè)子模塊。舉例來說，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示城市間開車行經(jīng)的距離，該算法可以用來找到兩個(gè)城市之間的最短路徑。

該算法的輸入包含了一個(gè)有權(quán)重的有向圖 G，以及G中的一個(gè)來源頂點(diǎn)S。我們以 V 表示 G 中所有頂點(diǎn)的集合。每一個(gè)圖中的邊，都是兩個(gè)頂點(diǎn)所形成的有序元素對。(u, v) 表示從頂點(diǎn) u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù) w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點(diǎn) u 到頂點(diǎn) v 的非負(fù)權(quán)重（weight）。邊的權(quán)重可以想像成兩個(gè)頂點(diǎn)之間的距離。任兩點(diǎn)間路徑的權(quán)重，就是該路徑上所有邊的權(quán)重總和。已知有 V 中有頂點(diǎn) s 及 t，Dijkst...