Morgen ist Maifeiertag, sind Sie bereit für Ihren Reiseführer? Heute führt Sie der Herausgeber durch einen Artikel über die Verwendung des Dijkstra-Algorithmus, der Ihnen dabei hilft, kostengünstige und sorgenfreie Reiserouten zu finden. Schauen Sie vorbei!
Fall:
Der Maifeiertag steht vor der Tür und Xiao Zhang ist reisebereit!
Ich habe die Flugtickets von verschiedenen Orten aus überprüft
Da mein Gehalt dieses Jahr sehr stark abgezogen wurde, hat Xiao Zhang nicht viel Geld und muss vorsichtig sein mit seinem Budget. Er möchte herausfinden, wie günstig es ist, in verschiedene Städte zu reisen.
【Nun, es besteht kein Grund, die Kosten einer Rückkehr zu bedenken. Xiao Zhang wollte dem Polizeionkel mitteilen, dass er Opfer von Menschenhandel war und dass er kostenlos zurückgeschickt werden würde. 】
Wenn er von Zhuhai nach Lhasa fliegen möchte, wie hoch sind die Mindestticketkosten? Lassen Sie uns über den Algorithmus sprechen, über den wir heute sprechen werden.
Der Dijkstra-Algorithmus ist ein typischer Single-Source-Kürzeste-Pfad-Algorithmus, der zur Berechnung des kürzesten Pfades von einem Knoten zu allen anderen Knotenpfaden verwendet wird. Das Hauptmerkmal besteht darin, dass es sich vom Startpunkt bis zum Endpunkt Schicht für Schicht nach außen ausdehnt. Die zeitliche Komplexität des Dijkstra-Algorithmus beträgt O(N^2).
Dijkstra wurde am 11. Mai 1930 in einer Intellektuellenfamilie in Rotterdam, Niederlande, geboren. Sie war das dritte von vier Brüdern und Schwestern. Sein Vater war Chemiker und Erfinder und Präsident der Niederländischen Chemischen Gesellschaft. Seine Mutter ist Mathematikerin. Er entwarf und implementierte erfolgreich einen effizienten Algorithmus, um den kürzesten Weg zwischen zwei Orten mit Hindernissen zu finden. Dieser Algorithmus wurde „Dijkstra-Algorithmus“ genannt und löste ein sehr kritisches Problem, nämlich das Problem der Bewegungspfadplanung Heute.
Verwandte Tutorials: Bilder von Data Structure Adventure
Zu den Städten, die direkt mit Zhuhai verbunden sind, gehören Shanghai, Peking, Guangzhou und Chongqing, dann Die Flugticketpreise von Zhuhai in andere Städte sind wie folgt (wenn es keine direkte Verbindung gibt, markieren wir unendlich): 
Es ist ersichtlich, dass Guangzhou unter diesen vier Städten die hat niedrigster Preis, also lasst uns von Guangzhou umsteigen
Die Städte, die direkt mit Guangzhou verbunden werden können, sind Peking und Lhasa. Dann gelten die Ticketpreise für den Anschluss Flüge von Zhuhai in andere Städte von Guangzhou sind wie folgt: (Es ist unmöglich zu wissen, ob Sie von Guangzhou aus umsteigen können)
Der Vergleich ergab, dass es 200 Yuan von Zhuhai nach Guangzhou und 600 Yuan sind Yuan von Guangzhou nach Peking, das sind nur 800 Yuan (es mag ein Zeitverlust sein, aber wen interessiert das schon, Xiao Zhang ist arm und hat nur noch Zeit)
Es sind 1700 Yuan von Guangzhou nach Lhasa, also ist es definitiv nicht besser als dort ankommen.
Nach dieser Berechnung haben wir die günstigste Preisliste. 
Chongqing und Nanjing sind Städte, die direkt mit Shanghai verbunden sind, und Zhuhai ist mit anderen Städten verbunden Städte ab Shanghai Die Flugticketpreise in den Städten sind wie folgt: 
Beim Vergleich der Originalpreise haben wir festgestellt, dass der Transfer von Shanghai nach Chongqing und Nanjing günstiger ist 
Peking ist direkt nach Shanghai (Shanghai wurde markiert, es muss der günstigste Preis sein, in Tatsächlich gibt es keinen Sinn zu vergleichen), Hangzhou und Lhasa, die Preise wie folgt: 
Der Preis nach Lhasa ist der niedrigste Preis nach Peking 800 + Peking-> Die Preise von 1400 in Lhasa (2200) sind höher als 1700, und 800 + 500 = 1300 nach Hangzhou, dann ist die Mindestpreisliste wie folgt
Nanjing kann nur direkt nach Hangzhou fliegen, 
Der Preis ab Von Nanjing nach Hangzhou sind es 1100, was ein gutes Angebot ist
Die einzige Direktverbindung von Chongqing ist Nanjing, und die Fahrt nach Nanjing kostet 1000 + 400 = 1400 Yuan, was im Vergleich zu den ursprünglichen 800 Yuan nach Nanjing definitiv nicht kosteneffektiv ist
Hangzhou kann nur nach Shanghai fahren, und der Preis ist höher als Shanghai
Dann kostet das günstigste Flugticket nach Lhasa 1.700 Yuan.
1) Verwenden Sie 0, 1, 2, , 7, um Zhuhai, Shanghai, Peking, Guangzhou, Chongqing, darzustellen. bzw. Hangzhou, Lhasa.
2) Verwenden Sie ein zweidimensionales Array von Preisen [8][8], um Flugpreise darzustellen: Preise[i][j] = Direktflugpreis von i nach j (wenn kein Flug stattfindet, wird er als ∞ aufgezeichnet )
3) Verwenden Sie ein Array „minPrice“, um die Mindestkosten für Flugtickets von Zhuhai in jede Stadt aufzuzeichnen:
4) Verwenden Sie ein Array-Flag, um zu markieren, ob die Stadt übertragen wurde
// 表示无穷大 即不可达
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();
}
stimmt mit dem obigen Push überein Ich hoffe, dieser Artikel kann Ihnen helfen.
Anhang-Quellcode:
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();
}
}Danke an den ursprünglichen Autor Halburt, ursprüngliche Adresse: https://www.cnblogs.com/Halburt/p/10767389.html
Das obige ist der detaillierte Inhalt vonSo finden Sie mit dem Dijkstra-Algorithmus die günstigste Reiseroute für den 1. Mai. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Was sind die Unterschiede zwischen C++ und der C-Sprache?
Empfohlene Lernreihenfolge für C++ und Python
Kosteneffizienzanalyse des Lernens von Python und C++
Ist C-Sprache dasselbe wie C++?
Was ist besser, zuerst zu lernen, C-Sprache oder C++?
Der Unterschied und die Verbindung zwischen C-Sprache und C++
Chinesisches Änderungs-Tutorial für C++-Software
Kosteneffizienzanalyse des Lernens von Python, Java und C++
