Dijkstra（迪杰斯特拉）算法是典型的最短路徑路由算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。下面這篇文章就給大家介紹關(guān)于C++用Dijkstra算法(迪杰斯特拉算法)求最短路徑的方法，下面來一起看看吧。
算法介紹
迪杰斯特拉算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。
算法思想
按路徑長(zhǎng)度遞增次序產(chǎn)生算法：
把頂點(diǎn)集合V分成兩組：
（1）S：已求出的頂點(diǎn)的集合（初始時(shí)只含有源點(diǎn)V0）
（2）V-S=T：尚未確定的頂點(diǎn)集合
將T中頂點(diǎn)按遞增的次序加入到S中，保證：
（1）從源點(diǎn)V0到S中其他各頂點(diǎn)的長(zhǎng)度都不大于從V0到T中任何頂點(diǎn)的最短路徑長(zhǎng)度
（2）每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值
S中頂點(diǎn)：從V0到此頂點(diǎn)的長(zhǎng)度
T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長(zhǎng)度
依據(jù)：可以證明V0到T中頂點(diǎn)Vk的，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和
應(yīng)用舉例
（1）題目：編寫一個(gè)校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。
主要功能：1.設(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)：頂點(diǎn)表示景點(diǎn)，邊表示路徑等；
2.為客人提供圖中任意景點(diǎn)相關(guān)信息的查詢；
3.為客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)艘跃包c(diǎn)間的一條最短路徑。
要求：1.設(shè)計(jì)一個(gè)主界面；
2.設(shè)計(jì)功能菜單，供用戶選擇
3.有一定的實(shí)用性。
（2）設(shè)計(jì)思路：
1、該題主要有算法思路以及程序的邏輯思路，首先從邏輯思路講，進(jìn)入程序，首先設(shè)計(jì)一個(gè)主菜單，選項(xiàng)有景點(diǎn)信息查詢，最短路徑查詢以及顯示景點(diǎn)的平面視圖三個(gè)子菜單，然后根據(jù)用戶的輸入選擇的子菜單前的編號(hào)，分進(jìn)入不同的子菜單；該功能是由if….else if…. 語句實(shí)現(xiàn)。在景點(diǎn)信息查詢和最短路徑查詢子菜單下還有二級(jí)子菜單，都是列 出所有景點(diǎn)并在前面編號(hào)，查詢景點(diǎn)信息時(shí)，輸入景點(diǎn)前面的編號(hào)即可，查詢最短路徑時(shí)，先輸入起點(diǎn)的編號(hào)，再輸入終點(diǎn)的編號(hào)。而顯示景點(diǎn)視圖則調(diào)用景點(diǎn)平面圖函數(shù)即可顯 示。
2、算法思路主要是迪杰斯特拉算法的思路，利用迪杰斯特拉算法求最短路徑。
3、先定義好圖的儲(chǔ)存結(jié)構(gòu)，本題采用鄰接矩陣的方式來表示圖，并在主函數(shù)中初始化該圖；
4、定義三個(gè)全局一維數(shù)組，一個(gè)bool類型數(shù)組S用來記錄從v0到vi是否已經(jīng)確定了最短路徑，是則記S[i]=true ,否記S[i]= flase；一個(gè)int 類型數(shù)組Path用來記錄從v0到vi的當(dāng)前最短路徑上的vi的直接前驅(qū)頂點(diǎn)編號(hào)，若v 到vi之間有邊則記Path[i] = v的編號(hào)，否則記Path[i] = -1；最后一個(gè)數(shù)組D用來記錄從v0到vi之間的最短路徑長(zhǎng)度，存在則記v0到vi之間邊的權(quán)值或者權(quán)值和，否則記為MAX
5、定義一個(gè)求最短路徑的函數(shù)，傳入的參數(shù)為圖和起點(diǎn)，首先進(jìn)行初始化工作，初始化S數(shù)組全為false，D數(shù)組初始化為起點(diǎn)到各個(gè)頂點(diǎn)的權(quán)值，Path數(shù)組初始化為起點(diǎn)是否與各頂點(diǎn)有邊，有則記v0否則記-1；
6、然后進(jìn)行n-1次for循環(huán)，找出vo到其余n-1個(gè)頂點(diǎn)之間的最短路徑，比較當(dāng)前D數(shù)組中最小值，找到最小值的編號(hào)v，該編號(hào)就是從v0出發(fā)到所有頂點(diǎn)中距離最短的頂點(diǎn)編號(hào)，然后把S[v]的值置為true。說明從v0出發(fā)到頂點(diǎn)v已經(jīng)找到最短路徑；
7、接著就要更新D數(shù)組，因?yàn)镈數(shù)組是記錄最短路徑的，現(xiàn)在已經(jīng)找到了一個(gè)頂點(diǎn)的最短路徑，已該頂點(diǎn)v為中間點(diǎn)，判斷從該頂點(diǎn)v出發(fā)到剩下的頂點(diǎn)的路徑長(zhǎng)度加上該點(diǎn)到v0的路徑長(zhǎng)度是否小于直接從v0出發(fā)到其余頂點(diǎn)的路徑長(zhǎng)度，如果小于，則更新D[i]為以該頂點(diǎn)v為中間點(diǎn)求得的路徑長(zhǎng)度。更新Path[i] = v；即i的前驅(qū)不再是v0而是v;
8、循環(huán)（6）（7）兩步n-1次即可得到D數(shù)組，輸出D數(shù)組既是v0到所有頂點(diǎn)的最短路徑長(zhǎng)度；
（3）源代碼：
（4）運(yùn)行截圖：
總結(jié)
以上就是關(guān)于C++用Dijkstra算法(迪杰斯特拉算法)求最短路徑的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作帶來一定的幫助，如果有疑問大家可以留言交流。
聯(lián)系客服
