How to use dijkstra's algorithm to find the most economical travel route for May Day

Tomorrow is May Day. Are you ready for your travel guide? Today, the editor will take you through an article about using the dijkstra algorithm to help you easily find travel routes, which is affordable and worry-free. Come and take a look!

Case:

May Day is coming soon, and Xiao Zhang is ready to travel!

Checked the air tickets from various places

　
Because his salary was deducted severely this year, Xiao Zhang did not have much money and had to be careful with his budget. He wants to find out the lowest cost of going to various cities.
[Well, there’s no need to consider the cost of coming back. Xiao Zhang was going to tell the police uncle that he had been trafficked and he would be sent back for free. 】
If he wants to fly from Zhuhai to Lhasa, how much is the minimum ticket cost? Let’s talk about the algorithm we are going to talk about today.

Dijkstra algorithm

Dijkstra algorithm is a typical single-source shortest path algorithm, used to calculate the shortest path from one node to all other nodes. path. The main feature is that it expands outward layer by layer from the starting point until it reaches the end point. The time complexity of Dijkstra's algorithm is O(N^2).

Extension

Dijkstra was born on May 11, 1930, in an intellectual family in Rotterdam, the Netherlands. She was the third among four brothers and sisters. His father was a chemist and inventor who served as president of the Dutch Chemical Society. His mother is a mathematician. He successfully designed and implemented an efficient algorithm to find the shortest path between two locations with obstacles. This algorithm was named "Dijkstra's algorithm" and solved a very critical problem in robotics. The problem, namely the motion path planning problem, is still widely used today.

Related tutorials: Data Structure Adventure Picture Chapter

Algorithm Derivation

Make a table to record Zhuhai The minimum air ticket cost to each city

We started looking for cities that are directly connected from Zhuhai

The cities that are directly connected to Zhuhai include Shanghai, Beijing, Guangzhou, and Chongqing, then The air ticket prices from Zhuhai to other cities are as follows (if there is no direct connection, we mark infinity):

It can be seen that among these four cities, Guangzhou has the lowest price, so let’s transfer from Guangzhou

The cheapest way to transfer from Guangzhou

The cities that can be directly connected to Guangzhou are Beijing and Lhasa. Then the ticket prices for connecting flights from Zhuhai to other cities from Guangzhou are as follows: (It is impossible to know if you can transfer from Guangzhou)

Comparison found that it is 200 yuan from Zhuhai to Guangzhou and 600 yuan from Guangzhou to Beijing, which is only 800 yuan (it may be a loss of time, but who cares, Xiao Zhang is poor and only has time)
Transferring from Guangzhou, it’s 1700 to Lhasa, so it’s definitely not better than arriving there.
So we have the cheapest price list.

In addition to Guangzhou, let’s find the cheapest city to transfer from Shanghai - Shanghai

Chongqing and Nanjing are the cities directly connected to Shanghai, then Zhuhai can transfer to other cities from Shanghai The air ticket prices in the cities are as follows:

Comparing the original prices, we found that it is cheaper to transfer from Shanghai to Chongqing and Nanjing

Except for Guangzhou and Shanghai, then Let’s then look for the cheapest city for connecting flights - Beijing

Beijing direct to Shanghai (Shanghai has been marked, it must be the cheapest price, in fact, there is no meaning to compare), Hangzhou and Lhasa, the price As follows:

The price to Lhasa is the lowest price to Beijing 800 Beijing-> The sum of the prices of 1400 in Lhasa (2200) is higher than 1700, and 800 to Hangzhou 500 = 1300, then The lowest price list is as follows

In addition to Guangzhou, Shanghai, and Beijing, let’s find the cheapest city for connecting flights - Nanjing

Nanjing can only go directly to Hangzhou,

The price from Nanjing to Hangzhou It’s 1100, which is a good deal

In addition to Guangzhou, Shanghai, Beijing, and Nanjing, let’s find the cheapest city for connecting flights - Chongqing

The only direct connection from Chongqing is Nanjing , and it costs 1000 400 = 1400 yuan to go to Nanjing, which is definitely not cost-effective compared to the original 800 yuan to Nanjing.

Except for Guangzhou, Shanghai, Beijing, Nanjing, and Chongqing, then from us Then I looked for the city with the cheapest transfer - Hangzhou

Hangzhou can only go to Shanghai, and the price is higher than Shanghai

Finally I found Lhasa

Then the cheapest air ticket to Lhasa is 1,700 yuan.

Code implementation

Variable preparation

1) Use 0,1,2,...,7 to represent Zhuhai, Shanghai, Beijing, Guangzhou, Chongqing, Nanjing, respectively. Hangzhou, Lhasa.
2) Use a two-dimensional array prices [8][8] to represent flight prices: prices[i][j] = direct flight price from i to j (if there is no flight, it is recorded as ∞)
3) Use an array minPrice to record the minimum air ticket cost from Zhuhai to various cities:
4) Use an array flag to mark whether the city has been transferred

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

Data preparation

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

Initialize the direct flight to Hangzhou The price

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

Algorithm implementation

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

The running result

is consistent with the above push process. I hope this article can be helpful to you.

Attachment-Source code:

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

 
}

Thanks to the original author Halburt, original address: https://www.cnblogs.com/Halburt/p/10767389.html

The above is the detailed content of How to use dijkstra's algorithm to find the most economical travel route for May Day. For more information, please follow other related articles on the PHP Chinese website!