NOIP 템 플 릿 복습 (3) 최 단 로 3 대 거두 Floyd, Dijkstra 와 SPFA

NOIP 템 플 릿 복습 (3) 최 단 로 3 대 거두 Floyd, Dijkstra 와 SPFA
최 단 로 는 도 론 에서 중요 한 문제 로 noip 의 상고점 입 니 다. 여기 서 최 단 로 를 구 하 는 흔 한 세 가지 알고리즘 을 쓰 겠 습 니 다.
목차
1. Floyd 알고리즘
알고리즘 원리
『 8195 』 1.2 알고리즘 실현
2. Dijkstra 알고리즘
알고리즘 원리
『 8195 』 2.2 알고리즘 실현
3. SPFA 알고리즘
『 81955 』 3.1 알고리즘 원리
『 8195 』 3.2 알고리즘 실현
4. 총화
1. Floyd 알고리즘
『 8195 』 플 로 이 드 알고리즘 은 동적 계획 사상 을 바탕 으로 하 는 다 원 최 단 로 알고리즘 으로 그림 에서 각 노드 간 의 최 단 로 를 계산 할 수 있다.
1.1 알고리즘 원리
우선 우 리 는 노드 i 에서 j 사이 의 가장 짧 은 경로 (약간 인접 행렬 과 유사) 를 정의 할 수 있 습 니 다.그리고 상태 전이 방정식 을 얻 을 수 있 습 니 다.    이 알고리즘 코드 는 매우 쉽게 실현 되 지만 시간 복잡 도가 매우 높 아 \ (O (n ^ 3) \) 등급 에 이 르 렀 지만 일부 문제 에서 예비 처리 역할 을 할 수 있 습 니 다. 예 를 들 어 noip 2016 의 교실 바 꾸 기 등 입 니 다.
1.2 알고리즘 구현
코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int dis[1005][1005];//floyd           
void floyd(int n)
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    return ;
}
int main()
{
    memset(dis,0x3f,sizeof(dis));
    int n,m;
    scanf("%d %d",&n,&m);
    register int u,v,w;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&u,&v,&w);
        dis[u][v]=w; 
        dis[v][u]=w;
    }
    floyd(n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<

2. Dijkstra 알고리즘
    Dijkstra 알고리즘 은 네덜란드 컴퓨터 과학자 dijkstra 가 커피 를 마 실 때 발명 한 것 (%%%) 으로 단원 최 단 로 알고리즘 으로 출발점 에서 모든 점 까지 의 최 단 로 를 구 할 수 있다.
2.1 알고리즘 원리
    Dijkstra 알고리즘 의 사상 은 이미 구 한 가장 짧 은 경 로 를 이용 하여 알 수 없 는 경 로 를 업데이트 하 는 것 이다.구체 적 인 방법 은 먼저 원점 에서 가장 가 까 운 점 을 찾 는 것 이다. 그러면 반드시 원점 에서 이 점 까지 의 가장 작은 거 리 를 얻 을 수 있다.이 점 을 중심 으로 원점 에서 다른 노드 로 의 거 리 를 업데이트 하려 고 시도 합 니 다.이렇게 반복 하면 모든 점 의 최 단 거 리 를 구 할 수 있다.
    이 알고리즘 은 소박 하 게 실 현 된 시간 복잡 도 는 \ (O (n ^ 2) \ (n 은 노드 수량) 이지 만 우 리 는 소박 한 서법 에서 원점 에서 가장 가 까 운 점 을 찾 아 이런 데이터 구 조 를 쌓 아 실현 할 수 있 습 니 다. 그러면 시간 복잡 도 는 \ (O (n + m) logn) \ (m 는 변 의 수량) 이 고 \ (O (nlogn) \ 와 비슷 한 효율 적 인 알고리즘 이 라 고 할 수 있 습 니 다.
2.2 알고리즘 구현
최적화 후 코드 를 사용 하기 위해 서:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct node
{
    int to,val;
};
struct point
{
    int id,val;
    bool operator val>mid.val;
    }
};
vector q[1005];
priority_queue p;
int dis[1005];
bool vised[1005];
void dijkstra(int start)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vised,0,sizeof(vised));
    dis[start]=0;
    p.push((point){start,0});
    while(!p.empty())
    {
        int now=p.top().id;
        p.pop();
        if(vised[now])
        {
            continue;
        }
        vised[now]=1;
        int len=q[now].size();
        for(int i=0;i

3. SPFA 알고리즘
    SPFA 알고리즘 은 Shortest Path Faster Algorithm 의 약자 로, 말 그대로 최 단 로 를 구 하 는 알고리즘 으로 서남 교통 대학의 단판 정 에서 발견 됐다.사실은 Bellman - ford 알고리즘 의 대기 열 최적화 입 니 다.그것 은 정상 적 인 상황 에서 비교적 좋 은 시간 복잡 도 를 가지 고 있 으 며, 가장 중요 한 것 은 마이너스 회로 의 상황 도 처리 할 수 있다 는 것 이다.
3.1 알고리즘 원리
『 8195 』 이 알고리즘 의 원 리 는 동적 접근 법 입 니 다. 한 대열 을 유지 하고 그 중에서 노드 를 꺼 내 이완 작업 을 하 는 동시에 이완 작업 을 거 친 노드 를 대열 에 넣 습 니 다.이렇게 끊임없이 다가 오 면 결국 가장 짧 은 경 로 를 얻 을 수 있다.    이 알고리즘 의 시간 복잡 도 는 \ (O (em) \) 이 며, 그 중 \ (e \) 는 변 의 수량 이 며, m 는 각 점 의 진입 횟수 를 평균 합 니 다.단판 정 은 논문 에서 m 가 보통 2 보다 작 지만 실제 이 알고리즘 은 실제 응용 에서 매우 불안정 하고 시간 복잡 도가 높 을 때 낮 다 는 것 을 증명 했다.
3.2 알고리즘 구현
코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct node 
{
    int to,val;
};
vector q[1005];
queue p;
int dis[1005];
bool vised[1005];
void SPFA(int start)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vised,0,sizeof(vised));
    vised[start]=1;
    p.push(start);
    dis[start]=0;
    while(!p.empty())
    {  
        int now=p.front();
        p.pop();
        vised[now]=0;
        int len=q[now].size();
        for(int i=0;i

4. 총화
전체 적 으로 말 하면 SPFA 의 복잡 하고 불안정 하기 때문에 최 단 로 를 구 할 때 보통 최 적 화 된 Dijkstra 알고리즘 을 사용 하고 SPFA 는 마이너스 회 로 를 판단 하 는 데 많이 사용 된다.Floyd 알고리즘 은 일부 예비 처리 에 만 사 용 됩 니 다.
Over!