如何用dijkstra算法找到五一最省旅游路線(xiàn)

如何用dijkstra算法找到五一最省旅游路線(xiàn)？這個(gè)問(wèn)題可能是我們?nèi)粘W(xué)習(xí)或工作經(jīng)常見(jiàn)到的。希望通過(guò)這個(gè)問(wèn)題能讓你收獲頗深。下面是小編給大家?guī)?lái)的參考內(nèi)容，讓我們一起來(lái)看看吧！

案例：

查了查到各地的機(jī)票

　　
因?yàn)榻衲瓯豢酃べY扣得很慘，小張手頭不是很寬裕，必須精打細(xì)算。他想弄清去各個(gè)城市的最低開(kāi)銷(xiāo)。
【嗯，不用考慮回來(lái)的開(kāi)銷(xiāo)。小張準(zhǔn)備找警察叔叔說(shuō)自己被拐賣(mài)，免費(fèi)被送回來(lái)?！?br/>如果他想從珠海飛到拉薩，最少要花多少機(jī)票錢(qián)呢？下面就說(shuō)到我們今天要說(shuō)的這個(gè)算法。

迪杰斯特拉(Dijkstra)算法

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法的時(shí)間復(fù)雜度為O(N^2)。

擴(kuò)展

狄克斯特拉Dijkstra1930年5月11日生于荷蘭鹿特丹的一個(gè)知識(shí)分子家庭，在兄弟姊妹4人中排行第三。他的父親是一名化學(xué)家和發(fā)明家，曾擔(dān)任荷蘭化學(xué)會(huì)主席。他母親則是一位數(shù)學(xué)家。他成功地設(shè)計(jì)并實(shí)現(xiàn)了在有障礙物的兩個(gè)地點(diǎn)之間找出一條最短路徑的高效算法，這個(gè)算法被命名為“狄克斯特拉算法”，解決了機(jī)器人學(xué)中的一個(gè)十分關(guān)鍵的問(wèn)題，即運(yùn)動(dòng)路徑規(guī)劃問(wèn)題，至今仍被廣泛應(yīng)用。

相關(guān)教程：數(shù)據(jù)結(jié)構(gòu)探險(xiǎn)之圖篇

算法推導(dǎo)

做個(gè)表來(lái)記錄珠海到各個(gè)城市的最少機(jī)票開(kāi)銷(xiāo)

我們開(kāi)始找從珠海直達(dá)的城市

珠海直達(dá)的城市有上海、北京、廣州、重慶，那么珠海到其他城市的機(jī)票價(jià)格如下（無(wú)法直達(dá)的我們標(biāo)記無(wú)窮大）：

可以看出，這4個(gè)城市中廣州價(jià)格最低，那我們就從廣州轉(zhuǎn)機(jī)吧

從機(jī)票最便宜的廣州轉(zhuǎn)機(jī)

廣州能直達(dá)的城市有北京、拉薩，那么珠海從廣州轉(zhuǎn)機(jī)到達(dá)其他城市的機(jī)票價(jià)格如下：（無(wú)法知道就能從廣州轉(zhuǎn)機(jī)）

對(duì)比發(fā)現(xiàn)從珠海到廣州 200 ，廣州到北京600，算下來(lái)才800塊錢(qián)（可能時(shí)間花銷(xiāo)上損失，管他呢，小張窮的只剩下時(shí)間了）
從廣州中轉(zhuǎn)，到拉薩1700，那么肯定比到不了強(qiáng)。
這么算下來(lái)我們有最便宜的價(jià)格表了。

除了廣州，那再?gòu)奈覀冊(cè)僬肄D(zhuǎn)機(jī)最便宜的城市--上海

上海直達(dá)的城市重慶、南京，那么珠海從上海轉(zhuǎn)機(jī)到達(dá)其他城市的機(jī)票價(jià)格如下：

對(duì)比原來(lái)的價(jià)格，發(fā)現(xiàn)上海中轉(zhuǎn)到重慶、南京比較便宜

除了廣州、上海，那再?gòu)奈覀冊(cè)僬肄D(zhuǎn)機(jī)最便宜的城市--北京

北京直達(dá)上海（上海已經(jīng)被標(biāo)記了，肯定已經(jīng)是最便宜的價(jià)格，其實(shí)已經(jīng)沒(méi)有比較的意義）、杭州和拉薩，價(jià)格如下：

到拉薩的價(jià)格 即 到北京最低的價(jià)格800 + 北京 -> 拉薩 1400 的價(jià)格之和（2200）高于1700，到杭州 800 + 500 = 1300，那么最低價(jià)格表如下

除了廣州、上海、北京，那再?gòu)奈覀冊(cè)僬肄D(zhuǎn)機(jī)最便宜的城市--南京

南京只能直達(dá)杭州，

南京到杭州的價(jià)格為1100，劃算

除了廣州、上海、北京、南京，那再?gòu)奈覀冊(cè)僬肄D(zhuǎn)機(jī)最便宜的城市--重慶

重慶直達(dá)的只有南京，且到南京需要1000 + 400 = 1400元，和原來(lái)的到南京的800比，肯定不合算

除了廣州、上海、北京、南京、重慶，那再?gòu)奈覀冊(cè)僬肄D(zhuǎn)機(jī)最便宜的城市--杭州

杭州也只能到上海，且比上海價(jià)格高

最終找到拉薩

那么拉薩最便宜的機(jī)票就是1700元。

代碼實(shí)現(xiàn)

變量準(zhǔn)備

1）用0,1,2,. . . ,7分別表示珠海，上海，北京，廣州，重慶，南京，杭州，拉薩。
2）用一個(gè)二維數(shù)組 prices [8][8] 來(lái)表示航班價(jià)格：prices[i][j] = i到j(luò)的直飛價(jià)格（如無(wú)航班記作∞)
3）用一個(gè)數(shù)組minPrice來(lái)記錄珠海到各個(gè)城市的最少機(jī)票開(kāi)銷(xiāo)：
4）用一個(gè)數(shù)組flag標(biāo)記城市是否已經(jīng)轉(zhuǎn)機(jī)過(guò)

    //    表示無(wú)窮大 即不可達(dá)
    public static int NO_AIRPLANE = Integer.MAX_VALUE;
//    初始直飛價(jià)格表
    public int[][]  prices ;
    //    最優(yōu)轉(zhuǎn)機(jī)價(jià)格表
    public int[]   minPrice ;
    public boolean[] flag ;
    private int citySize;

數(shù)據(jù)準(zhǔn)備

 public static int[][] getPrices(){
        int ZH = 0,SH = 1, BJ = 2, GZ = 3,CQ = 4,NJ = 5, HZ = 6,LS  = 7;
        int[][] prices =  new int[8][8];
        //from Zhuhai
        prices[ZH][CQ] = 1100;
        prices[ZH][SH] = 600;
        prices[ZH][BJ] = 900;
        prices[ZH][GZ] = 200;
        //others
        prices[CQ][NJ] = 400;
        prices[SH][CQ] = 400;
        prices[SH][BJ] = 500;
        prices[SH][NJ] = 200;
        prices[BJ][SH] = 400;
        prices[BJ][HZ] = 500 ;
        prices[BJ][LS] = 1400;
        prices[GZ][BJ] = 600 ;
        prices[GZ][LS] = 1500 ;
        prices[NJ][HZ] = 300 ;
        prices[HZ][SH] = 200 ;
        for(int i = 0 ; i < 8 ; i++){
            for(int j = 0 ; j < 8 ; j++){
                if(prices[i][j] == 0){
                    prices[i][j] =  NO_AIRPLANE;
                }
            }
        }
        return prices;
    }

初始化杭州直飛的價(jià)格

//            初始化始發(fā)站價(jià)格表
        for(int i = 1; i < citySize;i++){
            minPrice[i-1] = prices[0][i];
        }

算法實(shí)現(xiàn)

private void dijkstra(){
        int min = Integer.MAX_VALUE;
        int minIdx = Integer.MAX_VALUE;
//        找到最小的價(jià)格
        for(int idx = 0 ; idx < minPrice.length ; idx ++ ) {
            if(!flag[idx] &&  minPrice[idx] < min ){
                min = minPrice[idx];
                minIdx =  idx ;
            }
        }
        if(minIdx == Integer.MAX_VALUE){
//            已經(jīng)沒(méi)有最小的了
            return ;
        }
        //標(biāo)記從該城市轉(zhuǎn)機(jī)
        flag[minIdx] = true;
        minIdx += 1;
        System.out.println("最小城市序號(hào)"+minIdx +" 價(jià)格"+ minPrice[minIdx -1]);
 //        獲取當(dāng)前城市的價(jià)格表
        int cityPrice =  minPrice[minIdx -1];
        int[] minCityPrices = prices[minIdx];
        for(int idx = 1 ; idx < citySize ; idx ++ ){
            int price = minCityPrices[idx];
//            如果從杭州到達(dá)該城市的價(jià)格 加上 idx城市轉(zhuǎn)機(jī)的價(jià)格 低于  從杭州到達(dá)idx城市的價(jià)格 則更新
            if(!flag[idx -1 ] && price != NO_AIRPLANE  && (cityPrice+ price) < minPrice[idx - 1]){
//            可達(dá)的城市到達(dá)的
                minPrice[idx - 1] = cityPrice+ price;
                System.out.println(idx+"更新最優(yōu)表：" + Arrays.toString(minPrice));
            }
        }
        dijkstra();
    }

運(yùn)行結(jié)果

跟上述推到過(guò)程一致，希望本文能對(duì)你有所幫助。

附件-源碼：

package a;
 
import java.util.Arrays;
 
/**
 * 　　　　　　　　┏┓　　　┏┓+ +
 * 　　　　　　　┏┛┻━━━┛┻┓ + +
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┃　　　━　　　┃ ++ + + +
 * 　　　　　　 ████━████ ┃+
 * 　　　　　　　┃　　　　　　　┃ +
 * 　　　　　　　┃　　　┻　　　┃
 * 　　　　　　　┃　　　　　　　┃ + +
 * 　　　　　　　┗━┓　　　┏━┛
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃ + + + +
 * 　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting
 * 　　　　　　　　　┃　　　┃ + 　　　　神獸保佑,代碼無(wú)bug
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃　　+
 * 　　　　　　　　　┃　 　　┗━━━┓ + +
 * 　　　　　　　　　┃ 　　　　　　　┣┓
 * 　　　　　　　　　┃ 　　　　　　　┏┛
 * 　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +
 * 　　　　　　　　　　┃┫┫　┃┫┫
 * 　　　　　　　　　　┗┻┛　┗┻┛+ + + +
 *
 * @Author:Halburt
 * @Date:2019-04-24 下午 5:47
 * @Description:
 */
public class DijkstraDemo {
 
    //    表示無(wú)窮大 即不可達(dá)
    public static int NO_AIRPLANE = Integer.MAX_VALUE;
//    初始直飛價(jià)格表
    public int[][]  prices ;
    //    最優(yōu)轉(zhuǎn)機(jī)價(jià)格表
    public int[]   minPrice ;
    public boolean[] flag ;
    private int citySize;
    /**
     * @param citySize 城市數(shù)量
     */
    public DijkstraDemo(int citySize){
        this.citySize = citySize;
//      prices = new int [citySize][citySize];
        flag  =  new boolean [citySize - 1];
        minPrice = new int[citySize - 1 ];
    }
    public static int[][] getPrices(){
        int ZH = 0,SH = 1, BJ = 2, GZ = 3,CQ = 4,NJ = 5, HZ = 6,LS  = 7;
        int[][] prices =  new int[8][8];
        //from Zhuhai
        prices[ZH][CQ] = 1100;
        prices[ZH][SH] = 600;
        prices[ZH][BJ] = 900;
        prices[ZH][GZ] = 200;
        //others
        prices[CQ][NJ] = 400;
        prices[SH][CQ] = 400;
        prices[SH][BJ] = 500;
        prices[SH][NJ] = 200;
        prices[BJ][SH] = 400;
        prices[BJ][HZ] = 500 ;
        prices[BJ][LS] = 1400;
        prices[GZ][BJ] = 600 ;
        prices[GZ][LS] = 1500 ;
        prices[NJ][HZ] = 300 ;
        prices[HZ][SH] = 200 ;
        for(int i = 0 ; i < 8 ; i++){
            for(int j = 0 ; j < 8 ; j++){
                if(prices[i][j] == 0){
                    prices[i][j] =  NO_AIRPLANE;
                }
            }
        }
        return prices;
    }
    public static void main(String[] args) {
        DijkstraDemo demo = new DijkstraDemo(8);
        demo.dijkstra(getPrices());
    }
 
    public void dijkstra(int[][]  prices ){
        this.prices = prices;
//        初始化
//            初始化始發(fā)站價(jià)格表
        for(int i = 1; i < citySize;i++){
            minPrice[i-1] = prices[0][i];
        }
        System.out.println("初始化最優(yōu)表：" + Arrays.toString(minPrice));
        dijkstra();
        System.out.println("最終最優(yōu)價(jià)格表：" + Arrays.toString(minPrice));
    }
 
    private void dijkstra(){
        int min = Integer.MAX_VALUE;
        int minIdx = Integer.MAX_VALUE;
//        找到最小的價(jià)格
        for(int idx = 0 ; idx < minPrice.length ; idx ++ ) {
            if(!flag[idx] &&  minPrice[idx] < min ){
                min = minPrice[idx];
                minIdx =  idx ;
            }
        }//=已經(jīng)沒(méi)有最小的了
        if(minIdx == Integer.MAX_VALUE){
            return ;
        }
        //標(biāo)記從該城市轉(zhuǎn)機(jī)
        flag[minIdx] = true;
        minIdx += 1;
        System.out.println("轉(zhuǎn)機(jī)城市序號(hào)"+minIdx +" 價(jià)格"+ minPrice[minIdx -1]);
       //獲取該城市轉(zhuǎn)機(jī)時(shí)飛往其他城市的價(jià)格表
        int cityPrice =  minPrice[minIdx -1];
        //獲取杭州飛往該城市的價(jià)格
        int[] minCityPrices = prices[minIdx];
        for(int idx = 1 ; idx < citySize ; idx ++ ){
            int price = minCityPrices[idx];
//            如果從杭州到達(dá)該城市的價(jià)格 加上 idx城市轉(zhuǎn)機(jī)的價(jià)格 低于  從杭州到達(dá)idx城市的價(jià)格 則更新
            if(!flag[idx -1 ] && price != NO_AIRPLANE  && (cityPrice+ price) < minPrice[idx - 1]){
//            可達(dá)的城市到達(dá)的
                minPrice[idx - 1] = cityPrice+ price;
                System.out.println(idx+"更新最優(yōu)表：" + Arrays.toString(minPrice));
            }
        }
        dijkstra();
    }
 
 
 

 
}

感謝各位的閱讀！看完上述內(nèi)容，你們對(duì)如何用dijkstra算法找到五一最省旅游路線(xiàn)大概了解了嗎？希望文章內(nèi)容對(duì)大家有所幫助。如果想了解更多相關(guān)文章內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道。