Dijkstra算法舉例分析

本篇內容主要講解“Dijkstra算法舉例分析”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Dijkstra算法舉例分析”吧!

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
最短路徑？其實就是字面意思，一個帶邊值的圖中從某一個頂點到另外一個頂點的最短路徑。
官方定義：對于內網圖而言，最短路徑是指兩頂點之間經過的邊上權值之和最小的路徑。
并且我們稱路徑上的第一個頂點為源點，最后一個頂點為終點。
由于非內網圖沒有邊上的權值，所謂的最短路徑其實是指兩頂點之間經過的邊數最少的路徑。

它的主要特點是以起始點為中心向外層層擴展(廣度優先搜索思想)，直到擴展到終點為止。

迪杰斯特拉算法時間復雜度為 0(n^2)；

算法在實現步驟上類似與 普利姆算法  從最原始頂點開始 一步一步求到所有頂點的最小距離；

但是如果我們要尋找另外一個點到所有點的距離最小值 就要重新運行一遍這個算法

#define maxV 9 //最大頂點數  
#define min 65535;  
void DJSTL(MGraph G， int pos) //pos 這點到其余個點距離最小值  
{  
    bool final[maxV];//判斷是否已經存到S集合中  
    int ShortPath[maxV];//一個點到其余點的距離 存儲的是長度  
    int PathArc[maxV];// 存儲最短路徑下標  
    for(int i = 0; i<G.numV; i++)  
    {  
        ShortPath[i] = G.arr[pos][i];  
        final[i] = false;  
        PathArc[i] = 0;  
    }  
    ShortPath[pos] = 0; //該點到自身距離  
    final[pos] = true; //將該店納入 final 集合中  
    //開始主循環每次求的pos這點要某個頂點的最短路徑  
    int k=0;  
    for(int v=1;v<G.numV; v++)  
    {  
        int min = 65535;  
  
        for(int w=0;w<G.numV;w++)  
        {  
            if(!final(w) && ShortPath[w]<min)  
            {//不是到本身的最短的一個點的距離，類似普里姆法  
                min = ShortPath[w];  
                k = w;  
            }  
        }  
        final[k] = true ;//將該點納入final數組中  
        for(int j=0;j<G.numV;j++)  
        {  
            if(!final[j] && (min+G.arr[k][j])<ShortPath[j])  
            {  
                ShortPath[j] = min+G.arr[k][j];  
                PathArc[j] = k;  
            }  
        }  
    }  
}

比如pos=0時求的 ShortPath{0，1，4，7，5，8，10，12，16}他表示V0 這個點到各個頂點的最短路徑數。比如V0->V8 = 16 V0->V7=12;

PathArc{0,0,1,4,2,4,3,6,7}   

PathArc[8]=7 表示V0->V8 終點V8的前驅頂點是V7 

PathArc[7]=6 表示V7前驅頂點是V6

PathArc[6]=3 表示V6前驅頂點是V3

PathArc[3]=4 表示V3前驅頂點是V4

PathArc[4]=2 表示V4前驅頂點是V2

PathArc[2]=1 表示V2前驅頂點是V1

PathArc[1]=0 表示V1前驅頂點是V0

最短路徑為V0->V1->V2->V4->V3->V6->V7->V8

到此，相信大家對“Dijkstra算法舉例分析”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！