Dijkstra의 알고리즘을 사용하여 노동절에 가장 경제적인 여행 경로를 찾는 방법

내일은 메이데이인데, 여행 가이드 준비는 되셨나요? 오늘은 에디터가 다익스트라(dijkstra) 알고리즘을 활용해 저렴하고 걱정 없이 여행 경로를 쉽게 찾는 방법에 대한 기사를 소개하겠습니다.

사례:

5월이 곧 다가오고 Xiao Zhang은 여행을 떠날 준비가 되었습니다!

여러 곳에서 항공권을 확인했어요

　
올해 월급이 많이 깎여서 장샤오 씨는 돈이 별로 없어서 예산 관리에 주의해야 해요. 그는 여러 도시에 가는 데 드는 비용이 가장 저렴한지 알아보고 싶어합니다.
【글쎄, 돌아오는 데 드는 비용을 고려할 필요는 없습니다. Xiao Zhang은 경찰 삼촌에게 자신이 납치되었다는 사실을 알리고 무료로 돌려보내려고 했습니다. ]
주하이에서 라사까지 비행기를 타고 가고 싶다면 최소 항공권 비용은 얼마인가요? 오늘 이야기할 알고리즘에 대해 이야기해보겠습니다.

Dijkstra 알고리즘

Dijkstra 알고리즘은 일반적인 단일 소스 최단 경로 알고리즘으로, 한 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 데 사용됩니다. 주요 특징은 시작점부터 끝점에 도달할 때까지 한 겹씩 바깥쪽으로 확장된다는 점입니다. Dijkstra 알고리즘의 시간 복잡도는 O(N^2)입니다.

Extension

Dijkstra는 1930년 5월 11일 네덜란드 로테르담의 지식인 가정에서 태어났습니다. 그녀는 네 형제 자매 중 세 번째였습니다. 그의 아버지는 네덜란드 화학 협회의 회장을 역임한 화학자이자 발명가였습니다. 그의 어머니는 수학자이다. 그는 장애물이 있는 두 위치 사이의 최단 경로를 찾는 효율적인 알고리즘을 성공적으로 설계하고 구현했습니다. 이 알고리즘은 "Dijkstra 알고리즘"으로 명명되었으며 로봇 공학의 매우 중요한 문제, 즉 동작 경로 계획 문제를 해결했습니다. 오늘.

관련 튜토리얼: 데이터 구조 모험 사진

알고리즘 도출

주하이에서 여러 도시까지의 최소 항공권 비용을 기록하는 테이블 만들기

주하이에서 직항 도시를 찾기 시작했습니다.

주하이와 직접 연결된 도시에는 상하이, 베이징, 광저우, 충칭이 포함됩니다. 주하이에서 다른 도시까지의 항공권 가격은 다음과 같습니다(직접 연결이 없는 경우 무한대로 표시됩니다). 이 4개 도시 중 광저우가 가격이 가장 저렴하므로 광저우에서 환승하겠습니다
항공권이 가장 저렴한 광저우에서 환승

광저우와 직결 가능한 도시는 베이징과 라싸입니다. 그러면 티켓 가격이 나와요. 주하이에서 광저우에서 다른 도시로 가는 연결 항공편은 다음과 같습니다. (광저우에서 환승이 가능한지 알 방법이 없습니다)

비교해보면 주하이에서 광저우까지 200위안, 광저우에서 베이징까지 600위안입니다. . 총 800 위안입니다 (시간이 낭비 될 수도 있고, Xiao Zhang은 가난하고 시간 만 남았습니다) 광주에서 라사로 환승 1700 위안, 그러면 확실히 Da Dao보다 낫지 않습니다.

이 계산에 따르면 가장 저렴한 가격표가 있습니다.

광저우 외에 연결편이 가장 저렴한 도시인 상하이를 찾아보자 - 상하이

상하이와 직결되는 충칭과 난징 도시, 그러면 상하이에서 다른 도시로 가는 주하이의 연결편 티켓 가격은 다음과 같습니다. :

원래 가격과 비교해 보니 상하이에서 충칭, 난징으로 환승하는 것이 더 저렴한 것으로 나타났습니다

광저우와 상하이를 제외하고 가장 저렴한 환승 도시를 찾아보자 - 베이징

베이징은 직행 상하이(상하이가 표시되어 있는데 틀림없이 가장 저렴한 가격, 사실 비교의 의미는 없음), 항저우와 라사 가격은 다음과 같습니다.

라사 가격은 베이징 최저가입니다. 800 + 베이징 -> 라싸 1400(2200)의 가격 합이 더 높음 1700에서 항저우 800 + 500 = 1300, 최저 가격표는 다음과 같습니다

광저우, 상하이, 베이징을 제외하고 경유 항공권이 가장 저렴한 도시를 찾아보자 - 난징

난징은 항저우로만 직항만 갈 수 있는데,

난징에서 항저우까지의 가격은 1100인데 가격이 착하다

광저우와 상하이, 베이징, 난징을 제외하고 충칭에서 항공편을 환승할 수 있는 가장 저렴한 도시를 찾아보겠습니다.

충칭에서 직접 연결되는 유일한 노선은 난징이며, 난징까지 가는 데 비용은 1000 + 400 = 1400위안입니다. 난징까지의 원래 800 위안과 비교하면 확실히 비용 효율적이지 않습니다

광저우, 상하이, 베이징, 난징, 충칭 외에도 연결 항공편이 가장 저렴한 도시를 찾자-항저우

항저우 만 갈 수 있습니다 상하이 행, 가격은 상하이보다 높습니다

드디어 라사를 찾았습니다

그러면 라사 행 가장 저렴한 항공권은 1,700 위안입니다.

코드 구현

변수 준비

1) 0,1,2,...,7을 사용하여 각각 주하이, 상하이, 베이징, 광저우, 충칭, 난징, 항저우, 라사를 나타냅니다.
2) 2차원 배열 가격[8][8]을 사용하여 항공편 가격을 나타냅니다. 가격[i][j] = i에서 j까지의 직항 항공편 가격(항공편이 없는 경우 로 기록)
3 ) minPrice 배열을 사용하여 주하이에서 다양한 도시까지의 최소 항공권 비용을 기록하려면:
4) 배열 플래그를 사용하여 도시가 연결되었는지 표시합니다.

    //    表示无穷大 即不可达
    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 
실행 결과
 
위의 푸시 과정과 동일합니다. 이 글이 도움이 되길 바랍니다. 
첨부-소스코드: 
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();
    }
 
 
 

 
}
원작자 Halburt에게 감사드립니다. 원주소: https://www.cnblogs.com/Halburt/p/10767389.html

위 내용은 Dijkstra의 알고리즘을 사용하여 노동절에 가장 경제적인 여행 경로를 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!