怎麼用dijkstra演算法找到五一最省旅遊路線

明天就是五一了，大家準備好旅遊攻略了嗎？今天小編帶大家了解一篇關於文章，用dijkstra演算法幫你輕鬆搞定旅遊路線，實惠又省心，快來看看吧！

案例：

五一快到了，小張準備去旅遊了！

查了查到各地的機票

　　
因為今年被扣工資扣得很慘，小張手頭不是很寬裕，必須精打細算。他想弄清楚去各個城市的最低開銷。
【嗯，不用考慮回來的開銷。小張準備找警察叔叔說自己被拐賣，免費送回來。 】
如果他想從珠海飛到拉薩，最少要花多少機票錢呢？下面就說到我們今天要說的這個演算法。

迪傑斯特拉(Dijkstra)演算法

Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特徵是以起始點為中心向外層層擴展，直到擴展到終點為止。 Dijkstra演算法的時間複雜度為O(N^2)。

擴展

狄克斯特拉Dijkstra1930年5月11日生於荷蘭鹿特丹的一個知識分子家庭，在兄弟姊妹4人中排行第三。他的父親是化學家和發明家，曾擔任荷蘭化學會主席。他母親則是一位數學家。他成功地設計並實現了在有障礙物的兩個地點之間找出一條最短路徑的高效算法，這個算法被命名為“狄克斯特拉算法”，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛應用。

相關教學：資料結構探險之圖篇

#演算法推導

做表來記錄珠海到各個城市的最少機票開銷

我們開始找從珠海直達的城市

珠海直達的城市有上海、北京、廣州、重慶，那麼珠海到其他城市的機票價格如下（無法直達的我們標記無窮大）：

#可以看出，這4個城市中廣州價格最低，那我們就從廣州轉機吧

#從機票最便宜的廣州轉機

廣州能直達的城市有北京、拉薩，那麼珠海從廣州轉機到達其他城市的機票價格如下：（無法知道就能從廣州轉機）

對比發現從珠海到廣州200 ，廣州到北京600，算下來才800塊錢（可能時間花銷上損失，管他呢，小張窮的只剩下時間了）
從廣州轉，到拉薩1700，那麼肯定比到不了強。
這麼算下來我們有最便宜的價格表了。

除了廣州，那再從我們再找轉機最便宜的城市--上海

上海直達的城市重慶、南京，那麼珠海從上海轉機到達其他城市的機票價格如下：

對比原來的價格，發現上海中轉到重慶、南京比較便宜

除了廣州、上​​海，那再從我們再找轉機最便宜的城市--北京

北京直達上海（上海已經被標記了，肯定已經是最便宜的價格，其實已經沒有比較的意義）、杭州和拉薩，價格如下：

到拉薩的價格即到北京最低的價格800 北京-> 拉薩1400 的價格之和（2200）高於1700，到杭州800 500 = 1300，那麼最低價格表如下

除了廣州、上​​海、北京，那再從我們再找轉機最便宜的城市--南京

#南京只能直達杭州，

#南京到杭州的價格為1100，划算

除了廣州、上​​海、北京、南京，那再從我們再找轉機最便宜的城市--重慶

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

除了廣州、上​​海、北京、南京、重慶，那再從我們再找轉機最便宜的城市--杭州

杭州也只能到上海，比上海價格高

最終找到拉薩

那麼拉薩最便宜的機票就是1700元。

程式碼實現

變數準備

1）用0,1,2,. . . ,7分別表示珠海，上海，北京，廣州，重慶，南京，杭州，拉薩。
2）用一個二維陣列prices [8][8] 來表示航班價格：prices[i][j] = i到j的直飛價格（如無航班記作∞)
3）用一個陣列minPrice來記錄珠海到各個城市的最少機票開銷：
4）用一個數組flag標記城市是否已經轉機過

    //    表示无穷大 即不可达
    public static int NO_AIRPLANE = Integer.MAX_VALUE;
//    初始直飞价格表
    public int[][]  prices ;
    //    最优转机价格表
    public int[]   minPrice ;
    public boolean[] flag ;
    private int citySize;

數據準備

 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;
    }

初始化杭州直飛的價格

//            初始化始发站价格表
        for(int i = 1; i < citySize;i++){
            minPrice[i-1] = prices[0][i];
        }

演算法實作

private void dijkstra(){
        int min = Integer.MAX_VALUE;
        int minIdx = Integer.MAX_VALUE;
//        找到最小的价格
        for(int idx = 0 ; idx < minPrice.length ; idx ++ ) {
            if(!flag[idx] &&  minPrice[idx] < min ){
                min = minPrice[idx];
                minIdx =  idx ;
            }
        }
        if(minIdx == Integer.MAX_VALUE){
//            已经没有最小的了
            return ;
        }
        //标记从该城市转机
        flag[minIdx] = true;
        minIdx += 1;
        System.out.println("最小城市序号"+minIdx +" 价格"+ minPrice[minIdx -1]);
 //        获取当前城市的价格表
        int cityPrice =  minPrice[minIdx -1];
        int[] minCityPrices = prices[minIdx];
        for(int idx = 1 ; idx < citySize ; idx ++ ){
            int price = minCityPrices[idx];
//            如果从杭州到达该城市的价格 加上 idx城市转机的价格 低于  从杭州到达idx城市的价格 则更新
            if(!flag[idx -1 ] && price != NO_AIRPLANE  && (cityPrice+ price) < minPrice[idx - 1]){
//            可达的城市到达的
                minPrice[idx - 1] = cityPrice+ price;
                System.out.println(idx+"更新最优表：" + Arrays.toString(minPrice));
            }
        }
        dijkstra();
    }

運行結果

#跟上述推到過程一致，希望本文能對你有幫助。

附件-原始碼：

package a;
 
import java.util.Arrays;
 
/**
 * 　　　　　　　　┏┓　　　┏┓+ +
 * 　　　　　　　┏┛┻━━━┛┻┓ + +
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┃　　　━　　　┃ ++ + + +
 * 　　　　　　 ████━████ ┃+
 * 　　　　　　　┃　　　　　　　┃ +
 * 　　　　　　　┃　　　┻　　　┃
 * 　　　　　　　┃　　　　　　　┃ + +
 * 　　　　　　　┗━┓　　　┏━┛
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃ + + + +
 * 　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting
 * 　　　　　　　　　┃　　　┃ + 　　　　神兽保佑,代码无bug
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃　　+
 * 　　　　　　　　　┃　 　　┗━━━┓ + +
 * 　　　　　　　　　┃ 　　　　　　　┣┓
 * 　　　　　　　　　┃ 　　　　　　　┏┛
 * 　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +
 * 　　　　　　　　　　┃┫┫　┃┫┫
 * 　　　　　　　　　　┗┻┛　┗┻┛+ + + +
 *
 * @Author:Halburt
 * @Date:2019-04-24 下午 5:47
 * @Description:
 */
public class DijkstraDemo {
 
    //    表示无穷大 即不可达
    public static int NO_AIRPLANE = Integer.MAX_VALUE;
//    初始直飞价格表
    public int[][]  prices ;
    //    最优转机价格表
    public int[]   minPrice ;
    public boolean[] flag ;
    private int citySize;
    /**
     * @param citySize 城市数量
     */
    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;
//        初始化
//            初始化始发站价格表
        for(int i = 1; i < citySize;i++){
            minPrice[i-1] = prices[0][i];
        }
        System.out.println("初始化最优表：" + Arrays.toString(minPrice));
        dijkstra();
        System.out.println("最终最优价格表：" + Arrays.toString(minPrice));
    }
 
    private void dijkstra(){
        int min = Integer.MAX_VALUE;
        int minIdx = Integer.MAX_VALUE;
//        找到最小的价格
        for(int idx = 0 ; idx < minPrice.length ; idx ++ ) {
            if(!flag[idx] &&  minPrice[idx] < min ){
                min = minPrice[idx];
                minIdx =  idx ;
            }
        }//=已经没有最小的了
        if(minIdx == Integer.MAX_VALUE){
            return ;
        }
        //标记从该城市转机
        flag[minIdx] = true;
        minIdx += 1;
        System.out.println("转机城市序号"+minIdx +" 价格"+ minPrice[minIdx -1]);
       //获取该城市转机时飞往其他城市的价格表
        int cityPrice =  minPrice[minIdx -1];
        //获取杭州飞往该城市的价格
        int[] minCityPrices = prices[minIdx];
        for(int idx = 1 ; idx < citySize ; idx ++ ){
            int price = minCityPrices[idx];
//            如果从杭州到达该城市的价格 加上 idx城市转机的价格 低于  从杭州到达idx城市的价格 则更新
            if(!flag[idx -1 ] && price != NO_AIRPLANE  && (cityPrice+ price) < minPrice[idx - 1]){
//            可达的城市到达的
                minPrice[idx - 1] = cityPrice+ price;
                System.out.println(idx+"更新最优表：" + Arrays.toString(minPrice));
            }
        }
        dijkstra();
    }
 
 
 

 
}

感謝原作者Halburt，原文網址：https://www.cnblogs.com/Halburt/p/10767389.html

以上是怎麼用dijkstra演算法找到五一最省旅遊路線的詳細內容。更多資訊請關注PHP中文網其他相關文章！