最短路徑演算法介紹

　　1、從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法等。

　　2、定義：最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。演算法具體的形式包括：確定起點的最短路徑問題- 即已知起始結點，求最短路徑的問題。適合使用Dijkstra演算法。

　　3、確定終點的最短路徑問題- 與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。

　　4、確定起點終點的最短路徑問題- 即已知起點和終點，求兩結點之間的最短路徑。全域性最短路徑問題- 求圖中所有的最短路徑。適合使用Floyd-Warshall演算法。

　　以資料結構為例，最小生成樹和最短路徑的區別是最小生成樹能夠保證整個拓撲圖的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。最短路徑是從一點出發，到達目的地的路徑最小。

　　資料結構（datastructure）是計算機儲存、組織資料的方式，指相互之間存在一種或多種特定關係的資料元素的集合，往往同高效的檢索演算法和索引技術有關。大多數資料結構都由數列、記錄、可辨識聯合、引用等基本型別構成。通常情況下，精心選擇的資料結構可以帶來更高的執行或者儲存效率。資料結構意味著介面或封裝，一個數據結構可被視為兩個函式之間的介面，或者是由資料型別聯合組成的儲存內容的訪問方法封裝。資料結構是指相互之間存在著一種或多種關係的資料元素的集合和該集合中資料元素之間的關係組成。

　　1、設定系統中有五個程序，每一個程序用一個程序控制塊表示；

　　2、輸入每個程序的“優先數”和“要求執行時間”；

　　3、為了排程方便，將五個程序按給定的優先數從大到小連成就緒佇列。用一單元指出佇列首程序，用指標指出佇列的連線情況；

　　4、處理機排程總是選隊首程序執行。採用動態優先數演算法，程序每執行一次優先數就減“1”，同時將執行時間減“1”；

　　5、若要求執行時間為零，則將其狀態置為“結束”,且退出佇列；

　　6、執行所設計程式，顯示或列印逐次被選中程序的程序名以及程序控制塊的動態變化過程。