최 단 경로 (방향 도 있 음)

앞에서 가장 짧 은 경 로 를 쓴 무방 향도 조작 은 이번 에는 무방 향도 조작 이다. 하고 싶 은 말 은 예전 의 사고방식 에 따라 경 로 를 저장 하 는 것 이다. 항상 최 단 경로 에 따라 실현 할 수 없다.
순서대로 출력 합 니 다. 해당 경 로 를 저 장 했 을 뿐 순서대로 저장 하지 않 았 습 니 다. 이번 프로그램 은 다른 사람의 코드 로 경로 의 저장 방법 을 흡수 하 였 습 니 다.
갑자기 이 방법 이 이 루어 진 것 같 아 요. Dijsktra 는 제 가 저번 에 쓴 것 보다 훨씬 간결 해 요!!그래서 과감하게 배 웠 습 니 다. 약 한 채소 의 성장 은 신의 도움 과 떨 어 질 수 없습니다. 여기 있 습 니 다.
대 신 룸메이트 감사합니다!!!코드 를 붙 여 주세요. 저장 하 세 요.
P: 코드 와 알고리즘 은 모두 룸메이트 의 것 입 니 다. 공 부 했 습 니 다...:

/*
  0  ，weight[u,v]  u v       ，     dis[]

     ：    dis[0]  0，           ，                   (OK[] = 0)。

  n-1 ：
1                  tmp，              (OK[] = 1)。

2      tmp    k，  Relax(tmp,k)，    ，  dis[tmp]+weight[tmp,k]
#include 
#include 

const int IFINITY = 99999999;
const int N = 50;

int main()
{
    int map[N][N], final[N], D[N], parent[N];
    
    //    
    memset(final, 0, sizeof(final));
    memset(parent, -1, sizeof(parent));
    for(int i = 0; i < N; i++)
    {
            D[i] = IFINITY;
            for(int j = 0; j < N; j++)
                    map[i][j] = IFINITY;
            
    }
    D[0] = 0;
    
    int n, m, s, e, w;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++)
    {
            scanf("%d %d %d", &s, &e, &w);
            map[s][e] = w;
    }
    
    
   	//Dijsktra
    for(int i = 1; i <= n-1; i++)
    {
            int tmp = -1;
            for(int j = 0; j < n; j++)
                    if(final[j] == 0 && (tmp == -1 || D[tmp] > D[j]))
                                tmp = j;
            final[tmp] = 1;
    
            for(int k = 0; k < n; k++)
                    if(final[k] == 0 && map[tmp][k] != IFINITY && D[tmp] + map[tmp][k] < D[k])
                    {
                                D[k] = D[tmp] + map[tmp][k];
                                parent[k] = tmp;
                    }
    }
    
    //     
    for(int i = 1; i < n; i++)
    {
            int tmp = i;
            while(parent[tmp] != -1)
            {
                              printf("v%d\t", tmp);
                              tmp = parent[tmp];
            }
            if(parent[i] != -1)
            {
                         printf("v0
");
                         printf("v0 to v%d has a shortest distance of %d
", i, D[i]);
            }
    }
    
    system("pause");
    return 0;
}