[[417618]]

本文轉(zhuǎn)載自微信公眾號「bigsai」，作者bigsai。轉(zhuǎn)載本文請聯(lián)系程序員bigsai公眾號。

前言

大家好,我是bigsai,今天給大家講講Dijkstra算法，下次拿著這個算法找女神少繞路，有女朋友的可以試試行不行的通。

對于Dijkstra算法,很多人可能感覺熟悉而又陌生,可能大部分人比較了解bfs和dfs,而對dijkstra和floyd算法可能知道大概是圖論中的某個算法,但是可能不清楚其中的作用和原理,又或許,你曾經(jīng)感覺它很難,那么,這個時候正適合你重新認識它。

Dijkstra是啥?

其實Dijkstra(迪科斯徹)是一個人,被稱為結(jié)構(gòu)程序設(shè)計之父,他提出goto有害論、信號量、原語等,創(chuàng)造解決銀行家算法、哲學家進餐問題、Dijkstra算法等等,在1972年獲得圖靈獎(計算機界諾?爾獎),今天咱們就學習Dijkstra算法。

Dijkstra算法干啥的?

Dijkstra是用來求單源最短路徑的,也就是在一個圖中,從一個點計算到達其他點的最短距離,再形象一點,就是比如七夕你捧著鮮花去找女神,有點距離,在不堵?沒紅綠燈情況下怎么找到一條最短的路徑:

這不是一眼就能看出來嘛!還要什么算法?enum,如果路徑很多像這樣呢?

就拿上圖來說,如果各條路?度都已知,那么可以使用dijkstra算法計算你到圖中所有節(jié)點的最短距離(不過你想要的就是和女神的距離最近)。不過這個單源最短路徑你可能產(chǎn)生一些疑惑:

單源什么意思?

一個源頭,從一個頂點出發(fā),Dijkstra算法只能求一個頂點到其他點的最短距離而不能任意兩點。

和bfs求的最短路徑有什么區(qū)別?

bfs求的與其說是路徑,不如說是次數(shù)。因為bfs他是按照隊列一次一次進行加入相鄰的點,而兩點之間沒有權(quán)值或者權(quán)值相等(代價相同)。bfs求最短路徑一般無權(quán)值路徑(只代表聯(lián)通性)或者權(quán)值相等,僅僅用次數(shù)就能表示路徑?短的情況,最典型的就是迷宮問題bfs搜索移動一次路徑為1就加一次。

Dijkstra在處理具體實例的應用還是很多的,因為具體的問題其實帶權(quán)更多一些。比如一個城市有多個鄉(xiāng)鎮(zhèn),鄉(xiāng)鎮(zhèn)可能有道路,也可能沒有,整個鄉(xiāng)鎮(zhèn)需要聯(lián)通,如果想計算每個鄉(xiāng)鎮(zhèn)到a鎮(zhèn)的最短路徑,那么Dijkstra就派上了用場。

算法分析

對于一個算法,首先要理解它的運行流程,對于Dijkstra算法而言,首先要知道其適用條件和環(huán)境:

一個連通圖,若干節(jié)點(節(jié)點可能有數(shù)值),但是路徑一定有權(quán)值并且不能為負(否則Dijkstra就不適用)。

Dijkstra的核心思想是貪心算法的思想,那什么是貪心呢?

貪心算法(又稱貪婪算法)是指,在對問題求解時,總是做出在當前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,他所

做出的是在某種意義上的局部最優(yōu)解。

貪心算法不是對所有問題都能得到整體最優(yōu)解,關(guān)鍵是貪心策略的選擇,選擇的貪心策略必須具備無后效性,即某個狀態(tài)以前的過程不會影響以后的狀態(tài),只與當前狀態(tài)有關(guān)。

對于貪心算法,在很多情況都能用到,下面舉2個不恰當?shù)睦?

1 .上學時,每周只能帶5個蘋果,你想帶最多,那么選五個蘋果你每次都選最大的那個五次下來你就選的最重的那個。

2 .錢幣找零,指定幣值和相應的數(shù)量,用最少的數(shù)量湊?某金額。利用貪心策略,優(yōu)先選擇面值大的錢幣,直到湊?總金額。

3 .活動選擇問題,知道多個活動開始時間、結(jié)束時間,想在一個時間內(nèi)參加最多活動,按照活動結(jié)束時間遞增排序即可。

上面的策略雖然沒有很強的理論數(shù)學依據(jù),或者不太好說明,更像一種事實規(guī)律經(jīng)驗,并且對于貪心問題具體處理上大部分都需要排序,還可能會遇到規(guī)則繁雜的類排序。那么我們的Dijkstra是如何貪心的呢?對于一個點,求圖中所有點的最短路徑,如果沒有正確的方法胡亂想確實很難算出來,并且如果暴力匹配復雜度呈指數(shù)級上升不適合解決實際問題。那么我們該怎么想呢?

首先,Dijkstra算法實現(xiàn)上需要這些前提:

• Dijkstra處理的是帶正權(quán)值的有權(quán)圖,那么就需要一個二維數(shù)組(如果空間大用List數(shù)組)存儲各個點到點之間邊的權(quán)值大小 (鄰接矩陣或者鄰接表存儲) ，各個點距離初始化為無窮大。
• 需要一個boolean數(shù)組判斷哪些點已經(jīng)確定最短?度路徑,那些點沒有確定。用一個 int數(shù)組記錄距離(在算法執(zhí)行過程有些點最短路徑可能被多次更新)。
• 需要優(yōu)先隊列加入已經(jīng)確定點的周圍點。每次拋出從起點最短路徑的那個點,直到所有點路徑確定最短為止。

簡單的概括流程為:

第一步一般從選定點開始拋入優(yōu)先隊列(路徑一般為0),boolean數(shù)組標記0的位置(最短為0) , 然后0周圍連通的點拋入優(yōu)先隊列中(可能是node類),并把各個點的距離記錄到對應數(shù)組內(nèi)，此時周圍點只是等待調(diào)度可能是最短距離，也可能被更新。(如果小于就更新,大于就不動,初始第一次是無窮肯定會更新),第一次就結(jié)束了。

從等待調(diào)度隊列中拋出距離最近的那個點B(第一次就是0周圍鄰居)。這個點距離一定是最近可以確定的(所有權(quán)值都是正的,點的距離只能越來越?，而它的路徑是所有可能中的最小的)標記這個點為true表示已經(jīng)確定,并且將這個點的鄰居加入隊列(下一次等待調(diào)度點為隊列中原有的和這個點周圍未確定的鄰居),并同時判斷是否更新B點鄰居?度,如果小于則更新!

重復二的操作,直到所有點都確定。

算法實現(xiàn)

代碼實現(xiàn)上面有些繁瑣，但是也不是很復雜，這里給個Dijkstra算法實現(xiàn)代碼：

package 圖論; 
 
import java.util.ArrayDeque; 
import java.util.Comparator; 
import java.util.PriorityQueue; 
import java.util.Queue; 
import java.util.Scanner; 
 
public class dijkstra { 
    static class node 
    { 
        int x; //節(jié)點編號 
        int lenth;//長度 
        public node(int x,int lenth) { 
            this.x=x; 
            this.lenth=lenth; 
        } 
    } 
 
    public static void main(String[] args) { 
 
        int[][] map = new int[6][6];//記錄權(quán)值，順便記錄鏈接情況，可以考慮附加鄰接表 
        initmap(map);//初始化 
        boolean bool[]=new boolean[6];//判斷是否已經(jīng)確定 
        int len[]=new int[6];//長度 
        for(int i=0;i<6;i++) 
        { 
            len[i]=Integer.MAX_VALUE; 
        } 
        Queue<node>q1=new PriorityQueue<node>(com); 
        len[0]=0;//從0這個點開始 
        q1.add(new node(0, 0)); 
        int count=0;//計算執(zhí)行了幾次dijkstra 
        while (!q1.isEmpty()) { 
            node t1=q1.poll(); 
            int index=t1.x;//節(jié)點編號 
            int length=t1.lenth;//節(jié)點當前點距離 
            bool[index]=true;//拋出的點確定 
            count++;//其實執(zhí)行了6次就可以確定就不需要繼續(xù)執(zhí)行了  這句可有可無，有了減少計算次數(shù) 
            for(int i=0;i<map[index].length;i++) 
            { 
                if(map[index][i]>0&&!bool[i]) 
                { 
                    node node=new node(i, length+map[index][i]); 
                    if(len[i]>node.lenth)//需要更新節(jié)點的時候更新節(jié)點并加入隊列 
                    { 
                        len[i]=node.lenth; 
                        q1.add(node); 
                    } 
                } 
            } 
        }        
        for(int i=0;i<6;i++) 
        { 
            System.out.println(len[i]); 
        } 
    } 
    static Comparator<node>com=new Comparator<node>() { 
 
        public int compare(node o1, node o2) { 
            return o1.lenth-o2.lenth; 
        } 
    }; 
 
    private static void initmap(int[][] map) { 
        map[0][1]=2;map[0][2]=3;map[0][3]=6; 
        map[1][0]=2;map[1][4]=4;map[1][5]=6; 
        map[2][0]=3;map[2][3]=2; 
        map[3][0]=6;map[3][2]=2;map[3][4]=1;map[3][5]=3; 
        map[4][1]=4;map[4][3]=1; 
        map[5][1]=6;map[5][3]=3;     
    } 
} 

當然,dijkstra算法比較靈活,實現(xiàn)方式也可能有點區(qū)別,但是思想是不變的:一個貪心思路。dijkstra執(zhí)行一次就能夠確定一個點,所以只需要執(zhí)行點的總和次數(shù)即可完成整個算法。

一句話概況一下，就是從一個點開始找周圍最短的一個，更新相應數(shù)據(jù)，再找已經(jīng)確定直接連接的第二個最短點、第三個一直到所有點確定，dijkstra算法就完成了。