Dijkstra算法

2021-02-13 數學中國

　　Dijkstra(迪傑斯特拉)算法是典型的單源最短路徑算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這裡均採用永久和臨時標號的方式。注意該算法要求圖中不存在負權邊。

　　function [S,D]=minRoute(i,m,W)

　　%圖與網絡論中求最短路徑的Dijkstra算法 M-函數

　　%格式 [S,D]=minroute(i,m,W)

　　% i為最短路徑的起始點,m為圖頂點數,W為圖的帶權鄰接矩陣，

　　% 不構成邊的兩頂點之間的權用inf表示。顯示結果為：S的每

　　% 一列從上到下記錄了從始點到終點的最短路徑所經頂點的序號;

　　% D是一行向量，記錄了S中所示路徑的大小;

　　%例如

　　% clear;w=inf*ones(6);w(1,3)=10;w(1,5)=30;

　　% w(1,6)=100;w(2,3)=5;w(3,4)=50;w(4,6)=10;

　　% w(5,4)=20;w(5,6)=60;

　　% i=1;[s,d]=minroute(i,6,w)

　　dd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];dd=[0;i];

　　% dd的第二行是每次求出的最短路徑的終點，第一行是最短路徑的值

　　kk=2;[mdd,ndd]=size(dd);

　　while ~isempty(V)

　　[tmpd,j]=min(W(i,V));tmpj=V(j);

　　for k=2:ndd

　　[tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));

　　tmp2=V(jj);tt(k-1,:)=[tmp1,tmp2,jj];

　　end

　　tmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(:,1));

　　if tmp3==tmpd, ss(1:2,kk)=[i;tmp(tmp4,2)];

　　else,tmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);

　　if dd(2,tmp4)==ss(tmp6,tmp4)

　　ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];

　　else, ss(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)];

　　end;end

　　dd=[dd,[tmp3;tmp(tmp4,2)]];V(tmp(tmp4,3))=[];

　　[mdd,ndd]=size(dd);kk=kk+1;

　　end; S=ss; D=dd(1,:);

　

相關焦點

  • 數學建模方法-Dijkstra算法
    今天要講的是圖論中的一個經典的算法。是一種叫Dijkstra算法的東東。這個算法是幹什麼用的呢。首先大家先看下面這幅圖：          這個東西是什麼呢。我們可以這樣理解，假如A到F表示6個地點。那些連接線就是道路。
  • 如何使用python完成數學建模常見算法
    後面我們將介紹幾種常見數學建模算法的python實現，旨在展示python在本領域的強大威力。 1 問題描述 你希望通過幾種常見算法的實現，了解python在數學建模中的能力。
  • 經典算法:徹底理解 Dijkstra 算法
    ，請參考：經典算法：Dijkstra 算法初探本文由單源最短路徑路徑問題開始，而後描述Bellman-Ford算法，到具體闡述Dijkstra算法，闡述詳細剖析Dijkstra算法的每一個步驟，教你徹底理解此Dijkstra算法。
  • 路徑規劃_Dijkstra算法
    腦子裡閃過的算法裡面Dijkstra算法應該算是比較簡單且實用的了，本文就來舉個例子說明下這個算法，順便寫點腳本也可以用在自己玩的汽車仿真環境裡面。先介紹下這個算法，這個算法是荷蘭info的科學家Dijkstra在1956年發明的，用來在圖中尋找不同節點之間的最短路徑，最簡單的一個例子就是用來計算不同城市間的最短距離。
  • Dijkstra算法及實現(附代碼)
    Dijkstra算法是典型最短路算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。
  • 最短路徑:Dijkstra 算法和 Floyd 算法
    Dijkstra算法1.定義概覽Dijkstra(迪傑斯特拉)算法是典型的單源最短路徑算法，用於計算一個節點到其他所有節點的最短路徑。Dijkstra算法是很有代表性的最短路徑算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。注意該算法要求圖中不存在負權邊。問題描述：在無向圖 G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。
  • 淺談ACM算法學習與有效訓練
    1、提高編程能力　　2、學習算法，（讀書，讀論文，包括做一些題目驗證）　　3、準備好面臨將到來的挑戰（熟悉題型，調整心態）　　4、啟發思維。三、關於算法學習的一些建議：　　<1>算法學習是ACM比賽所要推廣或者要提倡的一個方面　　記得曾經路過某人的blog，上面說他作比賽的時候遇到了一個dijkstra，他沒做出來，然後評論到（大意）：我才不會花時間去搞明白「這種」算法。
  • 單源最短路徑-Dijkstra 算法
    Dijkstra(迪傑斯特拉)算法是典型的單源最短路徑算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。下面我們介紹一下Dijkstra 算法。Dijkstra 算法將帶權圖 G = (V, E)的頂點分為兩個集合：S 、V - S，其中頂點集 S 是已求出的最短路徑的終點集合（初始時 S = {s}）。
  • NOIP複賽知識點簡述及複賽算法總結!
    普及組必學1、模擬算法（暴力枚舉），按照題目的要求，題目怎麼說就怎麼做，保證時間和正確性即可。 2、搜索與回溯，主要的是DFS（深度優先搜索）和BFS（寬度優先搜索），基本沒有直接的暴力搜索。一般是記憶化搜索加剪枝，普及組第三題難度。
  • 最全 Python 算法實現資源匯總!
    ，自己寫算法的過程可以幫助我們更好地理解算法思路，不要輕視每一個算法，一些雖然看似容易，但可能有很多坑。為了幫助大家在這個假期能提高學習效率，進階 Python 技能，筆者為大家推薦了一份用 Python代碼實現算法的資源帖，涵蓋從入門到高級的各類算法。下文中，筆者首先對項目的整體內容進行了一個歸納，之後為大家選取了幾個內容比較豐富的部分，供大家更高效地使用這一資源。
  • 手把手教你用Python實現Dijkstra算法(偽代碼+Python實現)
    最短路問題Shortest Path Problem之前的文章中我們已經用迪傑斯特拉算法求解過Solomon算例了，今天是用該算法求解有5個點連通圖的最短路徑。大家可以看完這篇再回顧一下之前的文章。Dijkstra算法Dijkstra算法是一種動態規劃思想的算法：把所有的點都標記為臨時標號，每個點有兩個屬性：起點到這個點的最短距離和這個點的前序節點；將起始點的最短距離初始化為0，將其餘點的最短距離初始化為無窮大；從起始點開始，探索其子節點，更新子節點的最短距離和前序節點，當所有子節點都探索完成，則修改當前節點的標號為永久標號；選擇剩餘臨時標號的點中
  • Matlab 二維模擬退火算法最優路徑(主程序)
    這部分承接Dijkstra算法的基礎之上，先算出單源最短路徑(綠線)，之後把經過的每個虛線段分成
  • 5大必知的圖算法,附Python代碼實現
    在這篇文章中將為大家介紹一些重要的圖算法，以及Python 的代碼實現。將上圖中的連通分量算法近似看作一種硬聚類算法，該算法旨在尋找相關數據的簇類。舉一個具體的例子：假設擁有連接世界上任意城市的路網數據，我們需要找出世界上所有的大陸，以及它們所包含的城市。我們該如何實現這一目標呢？
  • 深度好文:改變了我們生活方式最有影響力的5種圖算法
    我們用於執行此操作的Connected Components算法是基於BFS / DFS的特殊情況。我不會在這裡談論它是如何工作的，但我們將看到如何使用Networkx啟動和運行代碼。從零售角度來看：假設，我們有很多客戶使用大量帳戶。我們可以使用Connected Components算法的一種方法是在我們的數據集中找出不同的家庭。
  • 你不知道的關於計算機大師 Dijkstra 的事情
    Dijkstra 自己也沒有想到這個 20 分鐘的發明會成為他最著名的成就之一，並且會被以他的名字命名為 Djikstra 算法。三年以後這個算法才首次發布，但當時的數學家們都不認為這能成為一個數學問題：兩點之間的路徑數量是有限的，其中必然有一條最短的，這算什麼問題 呢？在之後的幾十年裡，直到今天，這個算法被廣泛應用在各個行業。
  • 圖的最短路徑算法-Floyd算法-弗洛伊德算法
    Floyd算法又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法 在計算機科學中，Floyd-Warshall算法是一種在具有正或負邊緣權重（但沒有負周期）的加權圖中找到最短路徑的算法。算法的單個執行將找到所有頂點對之間的最短路徑的長度（加權）。
  • 評估算法及算法的時間複雜度
    文章導讀【對於一個給定的算法，通常要評估其正確性和運行效率的高低。算法的正確性評估不在本文範圍之內，本文主要討論從算法的時間複雜度特性去評估算法的優劣。】程序是用來解決問題的，是由多個步驟或過程組成的，這些步驟和過程就是解決問題的算法。
  • 貪心算法與近似算法
    使用這種算法能得到最優解嗎？ 答：種貪婪策略是，選擇可裝入卡車剩餘空間內的最大箱子，並重複這個過程，直到不能再裝入箱子為止。使用這種算法不能得到最優解。2.你要去歐洲旅行，總行程為7天。對於每個旅遊勝地，你都給它分配一個價值——表示你有多想去那裡看看，並估算出需要多長時間。你如何將這次旅行的價值最大化？請設計一種貪婪算法。使用這種算法能得到最優解嗎？
  • 【算法】決策樹與ID3算法
    決策樹(Decision Tree)算法是機器學習(Machine Learning)中分類算法中的一個重要算法，屬於監督學習(Supervised Learning)算法。決策樹算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。