---
title: Dijkstra
tags: 演算法
---
## Dijkstra

### 解決單源最短路徑（不能負權）

#### 貪心思想
> 每次都找最短路徑加入集合 -> 再從最短的出發
> 直到沒有點
> 類 bfs 走訪（相鄰）

PSEUDOCODE:

while ( 找到下一個點 ) :
    找未訪問過(白點) 路徑最短
    for(走訪 n 個點):
        if (和當前點聯通):
            更新路徑

### 優化
> 時間複雜度主要來自 **"提取最小值"**
> 可以使用 priority_queue 做優化
> 預設最大先排 要改成最小
> `priority_queue< mpair,vector<mpair> ,greater<mpair>>`

### 相關題目
UVa 534
(跳青蛙 -> 求單次(兩點間)最短)

#include <iostream>
#include <queue>
#include <cmath>
#include <iomanip>
using namespace std;
typedef pair<double,double> mpair;

class point{
    public:
        int x,y;
        double distance(point b){ return sqrt( (b.x-x)*(b.x-x) + (b.y-y)*(b.y-y)); }
};


int main()
{   
    int n,r=1;
    while(cin>>n,n){
    
        vector<point> stone(n);
        vector<vector<double> > graph(n,vector<double>(n));
        priority_queue< mpair,vector<mpair> ,greater<mpair>> djk;
        vector<bool> visted(n,0); 

        for(int i=0;i<n;i++)
            cin>>stone[i].x>>stone[i].y;
        
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                graph[i][j] =  stone[i].distance(stone[j]);  
        
        djk.push({0,0});
        double mindist = -1;
        while(!djk.empty()){
            int np = djk.top().second;
            visted[np] = true;
            mindist = max(djk.top().first,mindist);
            if(np == 1)
                break;
            
            
            djk.pop();

            for(int i = 0; i <n ;i++){
                if(!visted[i]){
                    djk.push({graph[np][i],i});
                }
            }

        }

        printf("Scenario #%d\nFrog Distance = %.3f\n\n",r++,mindist);
    }
    return 0;
}