So finden Sie mit dem Dijkstra-Algorithmus die günstigste Reiseroute für den 1. Mai

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.

Dijkstra-Algorithmus

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).

Erweiterung

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

Algorithmusableitung

Erstellen Sie eine Tabelle, um Zhuhai The aufzuzeichnen Mindestkosten für Flugtickets in jede Stadt

Wir begannen mit der Suche nach Städten, die direkt von Zhuhai aus verbunden sind

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

Transfer von Guangzhou, wo es die günstigsten Flugtickets gibt

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.

Neben Guangzhou suchen wir auch nach der günstigsten Stadt für Umsteigeflüge von Shanghai aus.

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

Außer Guangzhou und Shanghai, dann suchen wir nach der günstigsten Stadt für Anschlussflüge - Peking

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

Neben Guangzhou, Shanghai und Peking finden wir auch die günstigste Stadt für den Transfer von Flügen – Nanjing

Nanjing kann nur direkt nach Hangzhou fliegen,

Der Preis ab Von Nanjing nach Hangzhou sind es 1100, was ein gutes Angebot ist

Neben Guangzhou, Shanghai, Peking und Nanjing suchen wir auch nach der günstigsten Stadt für Anschlussflüge – Chongqing

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

Außer Guangzhou, Shanghai, Peking, Nanjing und Chongqing, dann von Suchen wir nach der Stadt mit dem günstigsten Transfer – Hangzhou

Hangzhou kann nur nach Shanghai fahren, und der Preis ist höher als Shanghai

Endlich haben wir Lhasa gefunden

Dann kostet das günstigste Flugticket nach Lhasa 1.700 Yuan.

Code-Implementierung

Variablenvorbereitung

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;

Datenvorbereitung

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

Initialisieren Sie den Hangzhou-Direktflug. Der Preis

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

Algorithmusimplementierung

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

Das laufende Ergebnis

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!