최 단 로 문제 DijKstra 알고리즘 Bellman - ford 와 spfa 알고리즘

DijKstra 알고리즘 의 핵심 은 하나의 배열 d [Max] 에 있 습 니 다. d [i] 는 i 라 는 노드 가 중앙 노드 에서 의 거 리 를 나타 내 는 것 입 니 다. 알고리즘 이 실현 하고 자 하 는 것 은 한 걸음 한 걸음 업데이트 d [Max] 입 니 다. 모든 점 이 방문 되 어 연결 되 어야 종료 할 수 있다 는 것 을 알 고 있 습 니 다.
준비 단계

int n,m,s,e;
int mp[210][210];
int d[210];
int vis[210];

n, m 는 n 개의 점, m 개의 변, s 는 시작 점 (중앙 노드 는 d [Max] 배열 과 관련) 이 고 가장 짧 은 길 을 원 하 는 점 은 e 이다.
mp [i] [j] 2 차원 배열 은 i 점 에서 j 점 까지 의 거 리 를 저장 합 니 다.
입력 및 삭제 단계

while(scanf("%d %d",&n,&m) == 2)
    {
        getchar();
        memset(vis,0,sizeof(vis));
        memset(d,0,sizeof(d));
        for(int i = 0;i < 210;i++)
        {
            for(int j = 0;j < 210;j++)
            {
                if(i == j)mp[i][j] = 0;
                else mp[i][j] = mp[j][i] = inf;
            }
        }

        for(int i = 0;i < m;i++)
        {
            scanf("%d %d %d",&a,&b,&x);
            getchar();
            if(mp[a][b] > x)mp[a][b] = mp[b][a] = x;//                ，        
            
        }
        scanf("%d %d",&s,&e);
        getchar();
        Dijkstra(s,e);
    }

mp 배열 을 업데이트 합 니 다. mp [i] [i] 할당 이 0 이 아 닌 나머지 할당 값 은 inf (비교적 큰 값) 입 니 다. 이것 은 알 수 없 는 4 거 리 를 표시 하고 후속 입력 업데이트 mp 를 편리 하 게 하기 위해 서 입 니 다.
업 데 이 트 를 입력 할 때 는 두 가지 다 중 상황 을 조심해 야 하 며, 마지막 으로 가장 짧 은 길 만 기록 하면 된다.
최 단 로 dijkscar 알고리즘 찾기

 int next;
    //    s
    for(int i = 0;i < 210;i++)
    {
        d[i] = mp[s][i];
    }
    vis[s] = 1;
    for(int i = 0;i < 210;i++)
    {
        //    
        int minnum = inf;
        for(int j = 0;j < 210;j++)
        {
            if(!vis[j] && d[j] < minnum)
            {
                minnum = d[j];
                next = j;
            }
        }
        if(minnum == inf)
        {
            break;
        }
        vis[next] = 1;
        //     
        for(int j = 0;j < 210;j++)
        {
            if(!vis[j] && d[j] > mp[next][j] + d[next])//    
            {
                d[j] = mp[next][j] + d[next];
            }
        }
    }
if(d[e] != inf)
    printf("%d
",d[e]);
else
    printf("-1
");

먼저 중앙 노드 s 가 연 결 된 가장자리 에 따라 1 파 d [i] 배열 을 업데이트 합 니 다. 그러면 한 개의 점 과 한 개의 선 이 생 겼 습 니 다. 그 다음 에 이 라인 에서 가장 짧 은 것 을 찾 은 다음 에 걸 어 갑 니 다. (vis 배열 업데이트) 그러면 두 개의 점 과 한 개의 선 이 이미 지 났 습 니 다. (강력 히 제안 합 니 다) 방금 찾 은 점 에 따라 연 결 된 변 에 따라 1 파 d [i] 를 업데이트 합 니 다.배열 (여기 서 전문 적 으로 이완 이 라 고 함) 은 모든 선 에 대해 판단 해 야 할 것 은 다음 에 연 결 된 점 이 방문 한 적 이 있 는 지, 이 선의 시작 (s 중앙 노드) 부터 끝 (첫 번 째 다음 에 연 결 된 점) 까지 의 거리 가 현재 d [
] 배열 에 저 장 된 것 이 작 아야 업데이트 할 필요 가 있 잖 아 요. (이것 도 처음에 mp 2 차원 배열 이 inf 로 초기 화 된 이유 입 니 다)
찾 을 수 없 을 때 까지 이렇게.
그러나 dijkscar 알고리즘 에 치 명 적 인 약점 이 있 습 니 다. 즉, 마이너스 회로 가 있 는 상황 이 발생 하면 vis 배열 로 인해 구 하 는 최 단 로 오 류 를 초래 할 수 있 습 니 다. 마이너스 회로 가 발생 하면 최 단 로 가 없 기 때 문 입 니 다.
여기 서 특히 주의해 야 한다. 평소에 우리 가 고려 해 야 할 것 은 모두 양 방향 변 이기 때문에 네가 입력 한 변 값 이 마이너스 라면 이미 마이너스 회로 이다.
여 기 는 hdu 2544 고전 템 플 릿 문 제 를 예 로 들 면
일단 준비 단 계 를 진행 하도록 하 겠 습 니 다.

int N,M;
struct edge
{
    int from;
    int to;
    int cost;
}e[10010];
int d[110];
void init()
{
    memset(e,0,sizeof(e));
}

이런 의 미 를 다 알 아 볼 수 있다 고 믿 습 니 다. bijkscar 알고리즘 과 차이 가 많 지 않 습 니 다.
다음은 입력 과 비우 기 단계 입 니 다.

while(scanf("%d %d",&N,&M) == 2)
    {
        getchar();
        if(!N && !M)break;
        init();
        for(int i = 1;i <= M * 2;i ++)
        {
            scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].cost);
            i++;
            e[i].from = e[i - 1].to;//   
            e[i].to = e[i - 1].from;
            e[i].cost = e[i - 1].cost;
            getchar();
        }
        if(Bellman(1,N))
        {
            printf("%d
",d[N]);
        }
        else
        {
            cout<

양 방향 변 의 입력 문 제 를 주의 하 시 면 됩 니 다.
다음은 Bellman - ford 알고리즘 입 니 다.

for(int i = 1;i <= N;i++)
    {
        if(i != s)d[i] = inf;
        else d[i] = 0;
    }

첫 번 째 독립 된 for 순환 은 d [s] 만 0 으로 업 데 이 트 됩 니 다.

for(int i = 2;i <= N;i++)
    {
        for(int j = 1; j <= M * 2;j++)
        {
            if(d[e[j].to] > d[e[j].from] + e[j].cost)
            {
                d[e[j].to] = d[e[j].from] + e[j].cost;
            }
        }
    }

그리고 두 번 째 독립 된 for 순환
i. 업데이트 횟수 를 제어 합 니 다. 매번 업데이트 할 때마다 한 점 의 최 단 로 를 확인 할 수 있 기 때 문 입 니 다. n 점 은 n 번 업데이트 가 필요 합 니 다.
j 가 제어 하 는 것 은 모든 변 을 옮 겨 다 니 는 것 이다.
내 려 온 이완 (최적화) 에 대한 판단 사상 은 dijkscar 와 유사 하 다.

    int flag = 1;
    for(int j = 1; j <= M * 2;j++)
    {
        if(  d[e[j].to] > d[e[j].from] + e[j].cost  )
        {
            flag = 0;
            break;
        }
    }
    return flag;

다음은 마이너스 회로 의 판단 이다.
네가 다시 한 번 업 데 이 트 를 진행 해라. 만약 업 데 이 트 를 할 수 있다 면 틀림없이 마이너스 회로 가 존재 할 것 이다
사실 당신 은 발견 할 수 있 습 니 다. 이 for 순환 은 분명히 이전 for 순환 에서 떼 어 낸 작은 부분 이 잖 아 요. 위 에 for 순환 의 i 초기 값 을 1 로 설정 하고 내부 에 판단 을 추가 하면 여 기 는 절약 할 수 있 고 이해 하기 편리 합 니 다 ~
여전히 2544 문제 입 니 다. 다음은 spfa 알고리즘 입 니 다. 가장 많이 사용 하 는 알고리즘 입 니 다.
spfa 는 점 을 겨냥 하여 조작 하 는 것 입 니 다.
점 을 겨냥 한 알고리즘 에 대해 우 리 는 두 가지 사고방식 으로 나 눌 수 있다. 첫 번 째 는 체인 식 전방 향 성 이 고, 두 번 째 는 2 차원 구조 체 동적 수조 이다.
먼저 체인 식 전방 향 성의 응용 을 되 돌아 보 겠 습 니 다.
준비 단계

using namespace std;
struct edge{
    //int from;
    int to;
    int cost;
    int reid;
}e[20010];
int N,M,cnt;
int vis[110];
int id[110];
int time[110];
int d[110];

reid 는 이 점 에 포 함 된 변 앞 뒤 를 연결 하 는 변수 입 니 다.
time 배열 은 마이너스 회로 가 있 는 지 없 는 지 를 판단 하 는 데 쓰 인 다.
입력 및 삭제

while(scanf("%d %d",&N,&M) != EOF)
    {
        getchar();
        if(!N && !M)break;
        init();
        for(int i = 1;i <= M;i++)
        {
            int a,b,x;
            scanf("%d%d%d",&a,&b,&x);
            getchar();
            add(a,b,x);//         ，                    
            add(b,a,x);

void add(int from,int to,int cost)
{
    e[cnt].to = to;
    e[cnt].cost = cost;
    e[cnt].reid = id[from];
    id[from] = cnt;
    cnt++;
}

void init()
{
    for(int i = 0;i < 110;i++)
    {
        d[i] = inf;
        id[i] = -1;
    }
    cnt = 0;
    memset(e,0,sizeof(e));
    memset(vis,0,sizeof(vis));
    memset(time,0,sizeof(time));
}

init () 함수 의 초기 화 를 살 펴 보 겠 습 니 다. d [i] 배열 은 최대 값 으로 초기 화 되 었 습 니 다. id [i] 배열 은 - 1 로 초기 화 되 었 습 니 다. 대표 적 인 의 미 는 i 점 이 연결 되 어 있 는 아래 표 시 는 - 1 입 니 다. 연 결 된 아래 표 시 를 알 수 없습니다. cnct 는 0 으로 초기 화 되 었 습 니 다. 모든 변 수 는 아래 표 시 된 변수 입 니 다.
 그리고 spfa 알고리즘

queue q;
    q.push(S);
    vis[S] = 1;
    d[S] = 0;
    int flag = 0;

먼저 중앙 노드 push 를 넣 고 이 점 을 찾 았 는 지 판단 한다. flag 는 마이너스 회로 가 있 는 지 없 는 지 판단 한다.

while(q.size())
    {
        int now = q.front();//q     ，             ：？
        q.pop();
        for(int i = id[now];~i;i = e[i].reid)
        {
            if(d[e[i].to] > d[now] + e[i].cost)
            {
                d[e[i].to] = d[now] + e[i].cost;

                if(!vis[e[i].to])
                {
                    vis[e[i].to] = 1;
                    time[e[i].to]++;
                    if(time[e[i].to] > N)
                    {
                        flag = 1;
                        break;
                    }
                    q.push(e[i].to);
                }
            }
        }
        if(flag)break;
        vis[now] = 0;//       ，             ，             ！
    }

튕 겨 나 온 첫 번 째 점 입 니 다. 첫 번 째 점 에 연 결 된 모든 변 을 옮 겨 다 니 며 d [i] 배열 을 업데이트 한 다음 에 연 결 된 점 을 관찰 하고 방문 상 태 를 업데이트 하 며 방문 횟수 를 업데이트 합 니 다.
만약 에 한 점 의 방문 횟수 가 N 보다 많 으 면 마이너스 회로 가 존재 한 다 는 뜻 이다. 원리 와 Bellman - ford 알고리즘 이 차이 가 많 지 않 고 마지막 으로 주의해 야 할 점 은 vis [i] 이다.
그 상 태 를 0 으로 다시 갱신 하 는 것 도 마이너스 회 로 를 판단 하기 위 한 것 이다.
quue 는 우선 순위 가 있 을 수 없습니다. 주어진 순서에 따라 중앙 노드 bfs 에서 밖으로 방문 하 는 것 입 니 다. 일단 흐 트 러 지면 d [i] 가 업데이트 되 지 않 았 습 니 다. 당신 의 다음 단계 입 니 다.
업데이트 가 진행 되 었 습 니 다.
다음은 대열 의 실현 이다.
준비 작업 을 보다

int dis[maxn];
int v,e;// ， 
queue q;
int flag[maxn];//            
int times[maxn];//           
//  
struct graph
{
    int s,e,w;
}es[maxn];

입력 한 것 은 생략 했 습 니 다.
다음은 spfa 로 들 어 갑 니 다.

for(i=1;i<=v;i++)
    {
        dis[i]=info;
        flag[i]=0;
        times[i]=0;
    }
    dis[s]=0;
    q.push(s);
    times[s]++;

한 파 를 초기 화한 다음 에 중앙 노드 에 대해 한 파 를 초기 화 합 니 다.

while(!q.empty())
    {
        int t = q.front();
        q.pop();
        flag[t]=0;
        for(i=1;i<=e;i++)
        {
            if(dis[es[i].e]>dis[es[i].s]+es[i].w)
            {
                dis[es[i].e]=dis[es[i].s]+es[i].w;
                if(flag[es[i].e]==0)
                {
                    q.push(es[i].e);
                    flag[es[i].e]=1;
                    times[es[i].e]++;
                    if(times[es[i].e]==v)
                        return false;//    //         ！！
                }
            }
        }
    }

대열 의 첫 번 째 점 을 꺼 내 면 이곳 의 flag 는 vis 입 니 다.
그 다음 에 모든 변 을 최적화 시 키 고 차이 가 많 지 않 은 원 리 는 여기 서 설명 하지 않 겠 다.