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 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).
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
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 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. 
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
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
Nanjing can only go directly to Hangzhou, 
The price from Nanjing to Hangzhou It’s 1100, which is a good deal
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.
Hangzhou can only go to Shanghai, and the price is higher than Shanghai
Then the cheapest air ticket to Lhasa is 1,700 yuan.
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; 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();
}
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!
What are the differences between c++ and c language
Recommended learning order for c++ and python
Cost-effectiveness analysis of learning python and c++
Is c language the same as c++?
Which is better to learn first, c language or c++?
The difference and connection between c language and c++
C++ software Chinese change tutorial
Cost-effectiveness analysis of learning python, java and c++
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
