floyd 알고리즘 (C 언어 인접 표)

종합 하여 서술 하 다
floyd 알고리즘 은 모든 점 간 의 최 단 경 로 를 구 하 는 데 사용 된다.
ABCD 네 개의 정점 에 대해 dis [n] [n] 으로 임의의 두 점 거 리 를 표시 합 니 다.
알고리즘:
1. 두 점 거리 초기 화, 자신 0, 경로 없 음 1000
2. A 점 가입 후 dis 를 업데이트 합 니 다.
3. B 가입, dis 업데이트.이전 단계 에 A 를 한 걸음 의 중간 점 으로 하 는 dis 가 모두 구 했 기 때문에 이 단 계 는 B 를 중간 점 으로 하고 AB 를 중간 점 으로 하 는 dis 를 동시에 구 할 수 있 습 니 다.
4. 순환
세 가지 순환 에서 K 는 바로 가 입 된 ABCD, i, j 대표 가 한 줄 한 줄 씩 스 캔 하여 dis [I] [k] + dis [k] [j] 와 dis [i] [j] 의 크기 를 비교 합 니 다.
데이터 구조

typedef struct Side// 
{
    int toVertex;//     
    int data;
    struct side *next;
}Side,*sLink;
typedef struct Vertex//  
{
    int data;
    sLink first;//    
}Vertex,AdjList[20];
typedef struct Graph// 
{
    AdjList adj;//    ，      ， .  ->
    int n,v;//   ，  
}Graph,*gLink;

창설

void createGraph(gLink g)
{
    int n,v,data;
    printf("         ");
    scanf("%d %d",&n,&v);
    g->n = n;
    g->v = v;
    int i;
    for(i=0;iadj[i].data = data;
        g->adj[i].first = NULL;
    }
    printf("      ");
    int v1,v2,da;
    for(i=0;itoVertex = v2;
        s->next = g->adj[v1].first;
        g->adj[v1].first = s;
        s->data = da;
    }
}

알고리즘

int dis[15][15];
void floyd(gLink g)
{
    int i,j,k;
    //   
    for(i=0;in;i++)
    {
        for(j=0;jn;j++)
        {
            dis[i][j]=1000;
        }
        dis[i][i]=0;
    }
    for(i=0;in;i++)
    {
        sLink s = g->adj[i].first;
        while(s)
        {
            dis[i][s->toVertex]=s->data;
            s=s->next;
        }
    }
    //  
    for(k=0;kn;k++)//  K           
    {
        for(i=0;in;i++)//  
        {
            for(j=0;jn;j++)//  
            {
                if(dis[i][k]+dis[k][j]k-->j
                {
                    dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
    //  
    for(i=0;in;i++)
    {
        for(j=0;jn;j++)
        {
            printf("%-5d",dis[i][j]);
        }
        printf("
");
    }
}

주 함수

int main()
{
    gLink g = (gLink)malloc(sizeof(Graph));
    createGraph(g);
    floyd(g);
    return 0;
}