怎么用dijkstra算法找到五一最省旅游路线

案例：

查了查到各地的机票　　因为今年被扣工资扣得很惨，小张手头不是很宽裕，必须精打细算。他想弄清去各个城市的最低开销。【嗯，不用考虑回来的开销。小张准备找警察叔叔说自己被拐卖，免费被送回来。】如果他想从珠海飞到拉萨，最少要花多少机票钱呢？下面就说到我们今天要说的这个算法。

迪杰斯特拉(Dijkstra)算法

扩展

相关教程：数据结构探险之图篇

算法推导

做个表来记录珠海到各个城市的最少机票开销

我们开始找从珠海直达的城市

珠海直达的城市有上海、北京、广州、重庆，那么珠海到其他城市的机票价格如下（无法直达的我们标记无穷大）：可以看出，这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算法找到五一最省旅游路线的详细内容，更多内容请关注技术你好其它相关文章！