최 단 경로 문제 Dijkstra 알고리즘 학습

#include 
#include 

#define MAXSIZE 100
#define MAXCOST 99
typedef struct

{
    int vertex[MAXSIZE];
    int edges[MAXSIZE][MAXSIZE];

} MyGraph;

void GrarhPrint(MyGraph*g,int n);
void CreateMGraph(MyGraph*g,int e,int n);
void Djikstra(MyGraph *g,int v0,int n);
void Ppath(int path[],int i,int v0);
void Dispath(int dist[],int path[],int s[],int v0,int n);

int main()
{
    MyGraph *g=(MyGraph*)malloc(sizeof(MyGraph));
    CreateMGraph(g,10,6);
    Djikstra(g,0,6);
    return 0;
}
void CreateMGraph(MyGraph*g,
                  int e,//  
                  int n //   
                 )

{
    int i,j,k,m;
    printf("Input data of vertex(0~n-1):
");

    for(i=0; ivertex[i]=i; //   0~n-1      
    }
    //      ，         
    for(i=0; ifor(j=0; jif(i==j)
                g->edges[i][j]=0;
            else
                g->edges[i][j]=MAXCOST;//99   
        }
    }
    //    ，       
    for(k=0; kprintf("Input edge of(i,j) and edge of size:");
        scanf("%d%d%d",&i,&j,&m);
        g->edges[i][j]=m;
    }
    GrarhPrint(g,n);
}
//   
void GrarhPrint(MyGraph*g,int n)
{
    int i=0;
    int j=0;
    for(i=0; ifor(j=0; jif(g->edges[i][j]==MAXCOST||i==j)
                printf("∞\t");
            else
                printf("%d\t",g->edges[i][j]);//               
        printf("
");
    }
}
void Djikstra(MyGraph *g,int v0,int n)
{
    int dist[MAXSIZE],path[MAXSIZE],s[MAXSIZE];
    int i,j,k,mindis;
    for(i=0; iedges[v0][i]; //V0 Vi         dist[i]
        if(g->edges[v0][i]//     ，MAXOST  v0 vi   
            path[i]=v0;//  vo vi             
        else
            path[i]=-1;//v0 vi   
        s[i]=0;//s[i]=0    vi  T 
    }
    s[v0]=1;//v0    S
    path[v0]=0;//v0              
    for(i=0; ifor(j=0; j//     T             vk
        {
            if(s[j]==0&&dist[j]1;//  vk    S 
        for(j=0; j//    v0   T     Vj     
        {
            if(s[j]==0)//  Vj   T 
            {
                if(g->edges[k][j]edges[k][j]+dist[k]//v0 Vj     V0 Vk Vk Vj      
                    dist[j]=g->edges[k][j]+dist[k];
                    path[j]=k;
                }
            }
        }
    }
    Dispath(dist,path,s,v0,n);
}
void Ppath(int path[],int i,int v0)
{//          （   V0）    
    int k;
    k=path[i];
    if(k!=0)//  Vk    V0 
    {
        Ppath(path,k,v0);//      Vk      
        printf("%d,",k);//    Vk
    }
}
void Dispath(int dist[],int path[],int s[],int v0,int n)
{   //      
    int i;
    for(i=0;iif(s[i]==1)//  Vi   S 
        {
            printf(" %d %d        :%d,   :",v0,i,dist[i]);
            printf("%d,",v0);//        v0
            Ppath(path,i,v0);//          Vi
            printf("%d
",i);//        
        }
        else
            printf(" %d %d     
",v0,i);
    }
}

Dijkstra 알고리즘: 하나의 정점 i 부터 이 i 정점 에서 다른 정점 까지 의 거 리 를 한 배열 에 저장 하 는 것 같 습 니 다. 배열 아래 에 정점 번호 로 표시 하고 최소 값 을 선택 한 다음 에 아래 에 k 를 기록 한 다음 에 선택 한 k 정점 부터 k 정점 거 리 를 다른 정점 j 와 의 거 리 를 옮 겨 다 닙 니 다 (i 를 옮 겨 다 닐 수 없습니다).정점 i 에서 정점 j 까지 의 거리 와 정점 i 에서 정점 k 까지 의 거리 + 정점 k 에서 j 까지 의 거리 와 비교 하고 크 면 배열 의 정점 i 에서 j 까지 의 거 리 를 업데이트 합 니 다. 그렇지 않 으 면 변 하지 않 습 니 다.그러나 경 로 를 기록 하 는 것 을 기억 해 야 한다. 이 배열 은 최종 적 으로 정점 i 에서 다른 정점 까지 의 가장 짧 은 거 리 를 기록 할 뿐 어떤 정점 을 거 쳤 는 지 기록 할 수 없다. 코드 에서 배열 dist 가 기록 한 가장 짧 은 경 로 는 배열 path 가 기록 한 경로 이다.