sssp是指求從源點s到其它所有點的最短路徑問題。
定義,單源最短路徑問題,n屬性,
定義
最短路徑：對在權圖G=(V,E),從一個源點s到匯點t有很多路徑，其中路徑上權和最少的路徑，稱從s到t的最短路徑。
簡單講：找出連線兩個給定點的最低成本路徑。
單源最短路徑問題
令人驚訝的是，“單源單匯”與“單源多匯”兩個問題的算法複雜度是一樣的，有向、無向圖也一樣。統稱單源最短路徑問題。
n屬性
三角形性質
設源點s到點x、y的最短路徑長度為dis[x]、dis[y]。x與y之間的距離是len[x][y]，則有下面的“三角形定理”：
dis[x] + len[x][y] >= dis[y]
鬆弛
若在處理過程中，有兩點x、y出現不符合“三角形定理”，則可改進一下—鬆弛：
if ( dis[x]+len[x][y] < dis[y] )
dis[y] = dis[x]+len[x][y];
常用最短路徑算法：
Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法
