TXT

floyd

By Alfred Kennedy,2014-09-22 23:34
31 views 0
#include #include #include #include #define MAX_NAME 20 #define MAX_INFO 200 typedef int VRType; typedef char VertexType[MAX_NAME]; #define INFINITY 65535 #define MAX_VERTEX_NUM 50 typedef struct ...{ VRType adj; }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; struct MGraph ..

#include <stdio.h>

    #include <string.h>

    #include <stdlib.h>

    #include <conio.h>

    #define MAX_NAME 20

    #define MAX_INFO 200

    typedef int VRType;

    typedef char VertexType[MAX_NAME]; #define INFINITY 65535

    #define MAX_VERTEX_NUM 50

typedef struct

    ...{

    VRType adj;

    }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

struct MGraph

    ...{

    VertexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs;

    int vexnum;

    int arcnum;

    };

typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

//?µ?Ø??µãÔÚÍ?ÖеÄÐòºÅ

    int LocateVex(MGraph G,VertexType u) ...{

    int i;

    for(i =0; i< G.vexnum;i++) ...{

    if(strcmp(u,G.vexs[i]) == 0) return i;

    }

    return -1;

    }

    //read the file for creating the MGraph

    int CreateDN(MGraph &G)

    ...{

    FILE *fp;

    char start_city_name[MAX_NAME]; char end_city_name[MAX_NAME]; int distance_of_city = 0;

fp=fopen("./ukcities.txt","r");

//init MGraph data

//??µãÊýÁ?

    G.vexnum = 0;

//?õÊ???Á?µãÖ??äµÄ????ÐÅÏ?,ÔÚÕâÀï??ΪÁ??ö?ÇÊÐ?äµÄ?àÀë

    //INFINITYÔÚÕâÀïÓ?µ?Àí?âΪÎÞÇî?óµÄÒâË?,65535Ö?ÊÇÒ??ö?Î??Öµ

    for(int p=0;p<MAX_VERTEX_NUM;++p) for(int k=0;k<MAX_VERTEX_NUM;++k) G.arcs[p][k].adj = INFINITY;

for(p=0;p<MAX_VERTEX_NUM;++p)

    strcpy(G.vexs[p],"");

int m = 0;

    for(int i=0;i<MAX_VERTEX_NUM;i++) ...{

    fscanf(fp,"%s",start_city_name); if(LocateVex(G,start_city_name) == -1) ...{

    strcpy(G.vexs[m++],start_city_name); G.vexnum++;

    //printf("City Name: %s ", start_city_name); }

    fscanf(fp,"%s",end_city_name);

    if(LocateVex(G,end_city_name) == -1) ...{

    strcpy(G.vexs[m++],end_city_name); G.vexnum++;

    //printf("City Name: %s ", end_city_name); }

    fscanf(fp,"%d",&distance_of_city); int iStart = LocateVex(G,start_city_name); int iEnd = LocateVex(G,end_city_name); //Á??ö?ÇÊÐ?äµÄ?àÀë

    G.arcs[iStart][iEnd].adj = distance_of_city; }

    fclose(fp);

    return 1;

    }

    //×î?ÌÂ???µÄfloydËã??ʵÏÖ void ShortestPathByFloyd(MGraph G,DistancMatrix &D)

    ...{

    int u,v,w;

    for(v=0;v<G.vexnum;v++) ...{

    for(w=0;w<G.vexnum;w++) ...{

    D[v][w] = G.arcs[v][w].adj; }

}

    for(u=0;u<G.vexnum;u++) ...{

    for(v=0;v<G.vexnum;v++) ...{

    for(w=0;w<G.vexnum;w++) ...{

    if(D[v][u] + D[u][w] < D[v][w]) ...{

    D[v][w] = D[v][u] + D[u][w]; }

    }

    }

    }

    }

    int GetTheShortestDistance(char start_city[],char end_city[])

    ...{

    MGraph g;

    CreateDN(g);

    int i;

    for(i=0;i<g.vexnum;i++) ...{

    g.arcs[i][i].adj = 0;

    }

    DistancMatrix d;

    ShortestPathByFloyd(g,d); int nStart = LocateVex(g,start_city);

    int nEnd = LocateVex(g,end_city); if(nStart == -1)

    ...{

    printf("This city is not exist:%s ",start_city);

    return 0;

}

    if(nEnd == -1)

    ...{

    printf("This city is not exist:%s ",end_city);

    return 0;

    }

/**//*

    int j;

    for(i=0;i<g.vexnum;i++) {

    for(j=0;j<g.vexnum;j++) {

    if(d[i][j] == INFINITY) {

    printf("* ");

    }

    else

    {

    printf("%02d ",g.arcs[i][j]);

    }

    }

    printf(" ");

    }

    for(i=0;i<g.vexnum;i++) {

    for(j=0;j<g.vexnum;j++) {

    if(d[i][j] == INFINITY) {

    printf("* ");

    }

    else

    {

    printf("%03d ",d[i][j]); }

    }

    printf("@ ");

    }

    */

    if(d[nStart][nEnd] == INFINITY)

    ...{

return -1;

    }

    else

    ...{

    return d[nStart][nEnd];

    }

    }

    void main()

    ...{

    int key;

    char start_city[MAX_NAME];

    char end_city[MAX_NAME];

    do

    ...{

    printf("Enter the start city name: "); scanf("%s",start_city);

    printf("Enter the end city name: "); scanf("%s",end_city);

int nDistance = GetTheShortestDistance(start_city,end_city);

if(nDistance == -1)

    ...{

    printf("Can't find the path from %s to %s ",start_city,end_city);

    }

    else

    ...{

    printf("The shortest distance between %s and %s is %dkm

    ",start_city,end_city,nDistance); }

    printf("Press 'y' or 'Y' to continue or any key to quit! ");

    }

    while((key = getch()) == 'y' || key == 'Y');

}

Report this document

For any questions or suggestions please email
cust-service@docsford.com