Dijkstra算法|單源最短路徑|貪心算法

      單愿最短路徑描述：給定帶權有向圖G=(V,E),其中每條邊的權是非負實數。另外，還給定V中的一個頂點，稱之為源(origin)。現在要計算從源到其他各頂點的最短路徑的長度。這里的路徑長度指的是到達路徑各邊權值之和。

      Dijkstra算法是解單源最短路徑問題的貪心算法。Dijkstra算法的基本思想是：設置頂點集合S并不斷地做貪心選擇來擴充集合。一個頂點屬于集合S當且僅當從源點到該頂點的最短路徑長度已知。貪心擴充就是不斷在集合S中添加新的元素（頂點）。
      初始時，集合S中僅含有源(origin)一個元素。設curr是G的某個頂點，把從源到curr且中間只經過集合S中頂點的路稱之為從源到頂點curr的特殊路徑，并且使用數組distance記錄當前每個頂點所對應的最短路徑的長度。Dijkstra算法每次從圖G中的(V-S)的集合中選取具有最短路徑的頂點curr，并將curr加入到集合S中，同時對數組distance進行必要的修改。一旦S包含了所有的V中元素，distance數組就記錄了從源(origin)到其他頂點的最短路徑長度。

核心代碼：
      Dijkstra描述：帶權有向圖G=(V,E),V={1,2,3,...}。頂點origin是源。數組distance[index]表示當前源到頂點index的最短路徑長度。數組prev[index]表示源點到達index頂點最短路徑的前一個頂點[Dijkstra只能獲取最短路徑的長度，通過prev記錄前驅頂點可以很方便的獲取詳細的最短路徑]。
      數據結構與代碼：

  public struct DIJGraph
        {
            public int[] vexs;
            public int[][] arcs;
            public int num;
        }


    public static bool DIJKSTRA(int origin,DIJGraph g,int[] distance,int[] prev)
    {
        if (origin < 0 || origin >= g.num)
            return false;
        bool[] s = new bool[g.num];

        for (int index = 0; index < g.num; ++index)
        {
            s[index] = false;
            distance[index] = g.arcs[origin][index];
            prev[index] = (distance[index] == Int32.MaxValue) ? -1 : origin;
        }
        distance[origin] = 0;
        s[origin] = true;
        for (int i = 0; i < g.num; ++i)
        {
            int temp = Int32.MaxValue;
            int curr = 0;
            for (int index = 0; index < g.num; ++index)
            {
                if (!s[index] && distance[index] < temp)
                {
                    curr = index;
                    temp = distance[index];
                }
            }
            s[curr] = true;

            for (int index = 0; index < g.num; ++index)
            {
                if (!s[index] && g.arcs[curr][index] < Int32.MaxValue)
                {
                    int newDistance = distance[curr] + g.arcs[curr][index];
                    if (newDistance < distance[index])
                    {
                        distance[index] = newDistance;
                        prev[index] = curr;
                    }
                }
            }
        }
        return true;
    }</pre> <p>      <span style="color:#056746;">貪心選擇性質</span>|<span style="color:#056746;">最優子結構性質</span>是Dijkstra算法所具備的。不過，雖然Dijkstra算法是解決單源最短路徑的一款很優秀的算法，但是如果在圖中存在多條最短路徑，Dijkstra算法只能獲取路徑的長度，而無法給出最短路徑的詳細情況。即使在代碼中添加<span style="color:#0b80a7;">distance[index]</span>表示當前源到頂點index的最短路徑長度。數組<span style="color:#0b80a7;">prev[index]</span>來記錄前驅點，但是一旦存在多條最短路徑，我們只能獲取最先遇到的那條（或者最后遇到的那條路徑）<span style="color:#149bae;font-size:13px;">[往往，我們偏向于獲取的是最短路線而非路長]</span>。總之，Dijkstra算法還有許多改進的地方。<br />

      本文提供的核心代碼使用C#實現，您可以點擊下載獲取源代碼[點擊下載C語言實現代碼]。</p>
 本文系個人學習筆記|轉載請保留本文鏈接blog.iliyang.cn