preface
May Day is coming, Xiao Zhang is going to travel! I checked tickets to different places
Dijkstra algorithm
Dijkstra algorithm is a typical single-source shortest path algorithm used to calculate the shortest paths from one node to all other nodes. The main feature is to start from the center to the outer layer of expansion, until the extension to the end. Dijkstra's time complexity is O(N^2).Copy the codeextension
Dijkstra was born on May 11, 1930 in Rotterdam, The Netherlands, into an intellectual family, the third of four siblings. His father was a chemist and inventor who served as president of the Dutch Chemical Society. His mother was a mathematician. He successfully designed and implemented an efficient algorithm to find a shortest path between two places with obstacles, which was named "Dikstra algorithm", and solved a very key problem in robotics, namely motion path planning, which is still widely used today.Copy the codeAlgorithm is derived
Make a table to record the minimum cost of airfare from Zhuhai to various cities
We started looking for a direct city from Zhuhai
The direct flights from Zhuhai to Shanghai, Beijing, Guangzhou and Chongqing are as follows:
Transfer from The cheapest flight in Guangzhou
Guangzhou can direct to Beijing, Lhasa, then zhuhai transfer from guangzhou to other cities of the air ticket prices are as follows :(can not know the transfer from guangzhou)
The comparison found that from Zhuhai to Guangzhou 200, Guangzhou to Beijing 600, calculated down only 800 yuan (may be the loss of time cost, whatever, xiao Zhang is poor only time left) from Guangzhou transfer, to Lhasa 1700, then certainly better than not to reach. So we have the cheapest price list.
Besides Guangzhou, Shanghai is the cheapest city for connecting flights
Shanghai direct cities chongqing, Nanjing, then zhuhai transfer from Shanghai to other cities of the air ticket prices are as follows:
Comparison of the original price, found that Shanghai transfer to Chongqing, Nanjing is cheaper
In addition to Guangzhou and Shanghai, we can find the cheapest city for connecting flights — Beijing
Beijing direct to Shanghai (Shanghai is already marked as the cheapest price, in fact there is no meaning of comparison), Hangzhou and Lhasa, the price is as follows:
The price to Lhasa is the lowest price to Beijing 800 + Beijing -> Lhasa 1400 price sum (2200) higher than 1700, to Hangzhou 800 + 500 = 1300, so the lowest price list is as follows
In addition to Guangzhou, Shanghai, Beijing, then from us to find the cheapest transfer city – Nanjing
Nanjing can only go directly to Hangzhou,
In addition to Guangzhou, Shanghai, Beijing, Nanjing, then from us to find the cheapest transfer city – Chongqing
Chongqing direct only nanjing, and to Nanjing needs 1000 + 400 = 1400 yuan, and the original 800 to Nanjing, certainly not cost-effective
In addition to Guangzhou, Shanghai, Beijing, Nanjing, Chongqing, then from us to find the cheapest transfer city – Hangzhou
Hangzhou can only go to Shanghai, and the price is higher than Shanghai
Finally find Lhasa
Code implementation
Variable to
1) zhuhai, Shanghai, Beijing, guangzhou, chongqing, nanjing, hangzhou and Lhasa are represented by 0,1,2,… and 7 respectively. Prices [I][j] = the prices of direct flights from I to j (if there are no flights, denoted as ∞) 3) Use an array minPrice to record the minimum cost of air tickets from Zhuhai to various cities: 4) Use an array of flags to mark whether the city has changed planes
Public static int NO_AIRPLANE = integer.max_value; public static int NO_AIRPLANE = integer.max_value; Public int[][] prices; Public int[] minPrice; public boolean[] flag ; private int citySize;Copy the codeData 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;
}
Copy the codeInitial hangzhou direct flight price
// Initializes the destination price listfor(int i = 1; i < citySize; i++){ minPrice[i-1] = prices[0][i]; }Copy the codeAlgorithm implementation
private void dijkstra(){ int min = Integer.MAX_VALUE; int minIdx = Integer.MAX_VALUE; // Find the lowest pricefor(int idx = 0 ; idx < minPrice.length ; idx ++ ) {
if(!flag[idx] && minPrice[idx] < min ){
min = minPrice[idx];
minIdx = idx ;
}
}
if(minIdx == integer.max_value){// There is no minimumreturn; } // flag the transit from the city flag[minIdx] =true;
minIdx += 1;
System.out.println("Minimum City Number"+minIdx +"Price"+ minPrice[minIdx -1]); Int cityPrice = minPrice[minidx-1]; int[] minCityPrices = prices[minIdx];for(int idx = 1 ; idx < citySize ; idx ++ ){ int price = minCityPrices[idx]; // If the price from Hangzhou to the city plus the transfer price from IDX city is lower than the price from Hangzhou to IDX cityif(! flag[idx -1 ] && price ! = NO_AIRPLANE && (cityPrice+ price) < minPrice[idx-1]){ System.out.println(idx+"Update optimal table:" + Arrays.toString(minPrice));
}
}
dijkstra();
}
Copy the codeThe results
Download the source code
www.cnblogs.com/Halburt/p/1…
extension
How about going from Guangzhou to Chongqing? Or do I want to know the shortest path to any two of these eight cities? Dijkstra can only solve single-source paths. What if it cannot solve single-source paths? Please move to the shortest path Floyd algorithm to explain the derivation in detail.
PPT download
Wenku.baidu.com/view/871f04…