최 단 로 문제 소결

가장 짧 은 경로 문 제 는 도 론 연구 에서 전형 적 인 알고리즘 문제 로 그림 (결점 과 경로 로 구 성 된) 에서 두 결점 간 의 가장 짧 은 경 로 를 찾 는 데 목적 을 둔다.알고리즘 의 구체 적 인 형식 은 출발점 을 확정 하 는 가장 짧 은 경로 문제 - 즉, 시작 점 을 알 고 가장 짧 은 경 로 를 구 하 는 문제 이다.종점 을 확정 하 는 가장 짧 은 경로 문제 - 출발점 을 확정 하 는 문제 와 달리 이 문 제 는 종결 점 을 알 고 가장 짧 은 경 로 를 구 하 는 문제 입 니 다.무방 향도 에서 이 문 제 는 기점 을 확정 하 는 문제 와 완전히 같 고 유방 향도 에서 이 문 제 는 모든 경로 방향 을 반전 시 키 는 기점 을 확정 하 는 문제 와 같다.기점 종점 의 최 단 경로 문 제 를 확정 합 니 다. 즉, 기점 과 종점 을 알 고 두 결점 사이 의 최 단 경 로 를 구 합 니 다.
전역 최 단 경로 문제 - 그림 의 모든 최 단 경 로 를 구하 십시오.
그림 의 저장 구조:http://blog.csdn.net/ncepuzhuang/article/details/8445090
가장 많이 사용 되 는 경로 알고리즘 은 1. Floyd 알고리즘 입 니 다.
2. Dijkstra 알고리즘.
3. Bellman - ford 알고리즘.
4. SPFA 알고리즘.
다음은 한 명 씩 설명 하 겠 습 니 다.
1. Floyd 알고리즘.다 원, 무 마이너스 변 의 최 단 로 를 구하 다.실효 성 이 떨 어 지고 시간 복잡 도 O (V ^ 3).공간 복잡 도 는 O (N ^ 2) 입 니 다.임의의 두 점 사이 의 가장 짧 은 경 로 를 해결 하 는 알고리즘 이다.
http://blog.csdn.net/zhangxiangdavaid/article/details/38366923
핵심 코드:

void floyd(int n)
{
    int i,k,j;
    for(k=0; kmap[i][k]+map[k][j])//    i-->j     i-->k--->j     
                    map[i][j]=map[i][k]+map[k][j];//   i--->j     
}

2. Dijkstra 알고리즘 은 단원, 무 음 권 의 최 단 로 를 구한다.실효 성 이 비교적 좋 고 시간 복잡 도 는 O (V * V + E) 이다.욕심 법 으로 처리 되 지 않 은 최소 가중치 가 있 는 노드 를 선택 한 다음 에 그 아웃 사 이 드 를 이완 시킨다.
http://blog.csdn.net/zhangxiangDavaid/article/details/38360337
핵심 코드:

int dijkstra (int v)
{
    //   
    for (i=1;i<=n;i++)
    {
        vist[i]=0;
        dis[i]=map[v][i];
    }
    //  n-1          
    for (i=1;idis[pos]+map[pos][j])
                dis[j]=dis[pos]+map[pos][j];
        }
    }
    return dis[n];
}

3. Bellman - ford 알고리즘 은 단원 최 단 로 를 구하 고 마이너스 회로 (있 으 면 최 단 로 가 존재 하지 않 음) 가 있 는 지 판단 할 수 있 으 며 실효 성 이 좋 고 시간 복잡 도 O (VE) 가 있다.dijkstra 와 마찬가지 로 느슨 한 조작 을 바탕 으로 한다. 즉, 예상 되 는 최 단 경로 값 은 점점 더 정확 한 값 으로 대체 되 어 최 적 화 될 때 까지 이다.그것 의 원 리 는 그림 에 대해 n - 1 차 이완 작업 을 하여 가능 한 모든 최 단 경 로 를 얻 는 것 이다.dijkstra 보다 좋 은 점 은 변 의 가중치 가 마이너스 이 고 실현 이 간단 하 며 시간 복잡 도가 너무 높다 는 것 이 단점 이다.하지만 최적화 해 효율 을 높 일 수 있다.마이너스 링 은 마이너스 링 이 총 비용 을 제한 없 이 낮 출 수 있 기 때문에 n 차 조작 이 비용 을 낮 출 수 있다 는 것 을 발견 하면 반드시 마이너스 링 이 존재 한다 고 판정 했다.
핵심 코드:

  
struct node
{
    int u;//  
    int v;//  
    int w;//  
} p[inf];

int dis[inf];//                       
//                 
int nodenum,edgenum,source,i,j;

//   
void init ()
{

    scanf ("%d%d%d",&nodenum,&edgenum,&source);
    for (i=0; i<=nodenum; i++)
    {
        dis[i]=inf;
    }
    dis[source]=0;
    for (i=0; i dis[p[j].u] + p[j].w)//         dis  
            {
                dis[p[j].v] = dis[p[j].u] + p[j].w;
                flag=1;
            }
        }
        if (flag==0)
            break;
    }
    //    
    //    for        dis                  
    //                    
    for (i=0; i dis[p[i].u] + p[i].w)
        {
           
            return ;//       0    1       
        }
    }

}
  
 
   
   
  
4.SPFA   Bellman-Ford     ，      ，     O（kE）。（k<
 
   
   
  
    ：
 
   
   
  
void SPFA(int s，int e)  // s    e 
{
    int l,r,i;
    l=r=0;
    memset(vis,0,sizeof(vis));
    memset (dis,inf,sizeof (dis));
    dis[s]=0;
    q[r++]=s;//   
    vis[s]=1;//      1
    //     0
    while(l dis[p] + map[p][i])
            {
                dis[i] = dis[p] + map[p][i];
                if(vis[i]==0)
                {
                    q[r++] = i;
                    vis[i] = 1;
                }
            }
        }
        vis[p] = 0;
    }
    if(dis[e]!= inf)
        printf("%d
",dis[e]);
    else
        printf("-1
");
}