C++實現(xiàn)Dijkstra(迪杰斯特拉)算法
Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法,是廣度優(yōu)先算法的一種,用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴(kuò)展,直到擴(kuò)展到終點為止。其基本原理是:每次新擴(kuò)展一個距離最短的點,更新與其相鄰的點的距離。當(dāng)所有邊權(quán)都為正時,由于不會存在一個距離更短的沒擴(kuò)展過的點,所以這個點的距離永遠(yuǎn)不會再被改變,因而保證了算法的正確性。不過根據(jù)這個原理,用Dijkstra求最短路的圖不能有負(fù)權(quán)邊,因為擴(kuò)展到負(fù)權(quán)邊的時候會產(chǎn)生更短的距離,有可能就破壞了已經(jīng)更新的點距離不會改變的性質(zhì)。 Dijkstra算法能得出最短路徑的最優(yōu)解,但由于它遍歷計算的節(jié)點很多,所以效率低。 Dijkstra算法是很有代表性的最短路算法,在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹,如數(shù)據(jù)結(jié)構(gòu),圖論,運籌學(xué)等等。
Dijkstra 算法的時間復(fù)雜度為O(n^2)
空間復(fù)雜度取決于存儲方式,鄰接矩陣為O(n^2)
代碼實現(xiàn)
#include <stdio.h> #include <vector> #include <iostream> using namespace std; #define INF 0x7fffffff #define maxN 50 #define USE_C 1 #define NOT_USE_C 0 #define USE_CPP 1 int matrix[maxN][maxN]; void Dijkstra_cpp(vector<vector<int>>&vec,vector<int>& result,int v0){ vector<int> visited(vec.size(),0); int last_visitied = 0; result[0] = 0; for(int i =0;i<vec.size()-1;i++){ for(int j = 0;j<vec.size()-1;j++){ if(visited[i]==0){ if(vec[v0][j]!= 0){ int dist =vec[v0][j] +last_visited; if(dist<result[j]) result[j] = dist; } } } int minIndex = 0; while(visited[minIndex] == 1) minIndex++; for(int j = minIndex;j<vec.size();j++){ if(visited[j] ==0&&result[j]<result[minIndex]){ minIndex = j; } } last_visited = result[minIndex]; visited[minIndex] = 1; v0 = minIndex; } } int _tmain(int argc,_TCHAR* argv[]){ freopen("Dijkstra2Data.txt","r",stdin); int n; cin>>n; vector<vector<int>> vec(n,vector<int>(n,0)); for(i = 0;i<n;i++){ for(j = 0;j<n;j++){ cin>>vec[i][j]; } } vector<int> result(n,INF); Dijkstra_cpp(vec,result,0); for(int i =0;i<n;i++){ if(result[i] == INF) cout<<"INF"<<endl; else cout<<result[i]<<endl; } return 0; }
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
利用C語言實現(xiàn)任務(wù)調(diào)度的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用純C語言實現(xiàn)任務(wù)調(diào)度(可用于STM32、C51等單片機),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2023-04-04C程序?qū)崿F(xiàn)整數(shù)的素數(shù)和分解問題
這篇文章主要介紹了C程序?qū)崿F(xiàn)整數(shù)的素數(shù)和分解問題,對于算法的學(xué)習(xí)有不錯的借鑒價值,需要的朋友可以參考下2014-09-09C++11 模板參數(shù)的“右值引用”是轉(zhuǎn)發(fā)引用嗎
這篇文章主要介紹了C++11 模板參數(shù)的“右值引用”是轉(zhuǎn)發(fā)引用嗎,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05