基本概念
源點（Source）路徑的開始頂點
終點（Destination）路徑的最後一個頂點
單源最短路徑問題（SingleSource ShortestPaths Problem）給定一個帶權圖G=(VE)和圖中的一個源點v分別求出從v到圖G中其他每個頂點的最短路徑長度即路徑上權值的總和
單目標最短路徑問題（SingleDestination ShortestPaths Problem）找出圖中每一頂點v到某指定頂點u的最短路徑
單頂點對間最短路徑問題（SinglePair ShortestPath Problem）對於某對頂點u和v找出從u到v的一條最短路徑
所有頂點對間最短路徑問題（AllPairs ShortestPaths Problem）對圖中每對頂點u和v找出u到v的最短路徑問題
最短路徑（Shortest Path）即求兩個頂點間長度最短的路徑（該長度不是指路徑上邊數的總和而是指路徑上各邊權值的總和）
最短距離路徑是一個結點序列路徑的長度是其權值的和稱為距離所以最短路徑長度就是最短距離
最短路徑（迪傑斯特拉）算法
迪傑斯特拉（Dijkstra）提出了一個按路徑長度遞增的順序產生最短路徑的方法此方法的基本思想是把圖中所有頂點分成兩組每一組包括已確定最短路徑的頂點第二組包括尚未確定最短路徑的頂點按最短路徑長度遞增的順序逐個把第二組的頂點加到第一組中去直至從vi出發可以到達的所有頂點都包括到第一組中在此過程中總保持從vi到第一組各頂點的最短路徑長度都不大於從vi到第二組的任何頂點的最短路徑長度另外每一個頂點對應一個距離值第一組的頂點對應的距離值就是從vi到此頂點的只包括第一組的頂點為中間頂點的最短路徑長度
具體做法是
() 第一組S只包括源點v第二組T包括其他所有的頂點
() v對應的距離值為第二組的頂點對應的距離值是這樣確定的若圖中有邊＜vvj＞則vj的距離為此邊所帶的權值否則vj的距離值為一個很大的數（大於所有頂點間的路徑長度）然後每次從第二組的頂點中選一個其距離值為最小的vm加入第一組中
() 每往第一組加入一個頂點vm就要對第二組中的各個頂點的距離值進行一次修正修正的原則是若加進vm做中間頂點使從v到vj的最短路徑比不加vm的路徑為短則要修改vj的距離值
() 如此進行下去直到圖中所有頂點都包括在第一組中或再也沒有可加入到第一組中的頂點存在為止
From:http://tw.wingwit.com/Article/program/sjjg/201311/23546.html
