最短路径蓝桥杯

如下图所示，G是一个无向图，其中蓝色边的长度是 1、橘色边的长度是 2、绿色边的长度是 3。

则从 A到 S的最短距离是多少？   答案：6 

解题思路：

如果此类题目只需要答案，直接求解即可。

下面我们使用代码求解：

第一步：考虑怎么用计算机语言把图表示出来，图有几部分组成（1、点个数；2、分别是哪些点；3、点与点之间的距离（注意是有向边还是无向边））

第二步：递归找最短

#include
#include

#define max  100000 //表示两点之间没有连通
#define Vertex 20 //表示图的顶点 

//定义图 
typedef struct{
    int vertexNum;  
    char vertex[Vertex];  
    int arc[Vertex][Vertex];
}Graph,*PGraph;
//辅助数组
typedef struct{
    int distance;
    int path[Vertex];
}ArrayNode; 
//构造图 
void createGraph(PGraph G){
    int i,j;
    G->vertexNum=19;
    for(i=0;ivertexNum;i++){
        G->vertex[i]='A'+1;
    }
    for(i=0;ivertexNum;i++)
        for(j=0;jvertexNum;j++)
            G->arc[i][j] = 0;
    G->arc[0][1]=2;
    G->arc[0][2]=1;
    G->arc[0][3]=1;
    G->arc[0][4]=1;
    G->arc[1][0]=2;
    G->arc[1][6]=1;
    G->arc[1][9]=2;
    G->arc[2][0]=1;
    G->arc[2][3]=3;
    G->arc[2][5]=3;
    G->arc[3][0]=1;
    G->arc[3][2]=3;
    G->arc[3][4]=1;
    G->arc[3][6]=2;
    G->arc[3][7]=1;
    G->arc[3][8]=2;
    G->arc[4][0]=1;
    G->arc[4][3]=1;
    G->arc[4][7]=1;
    G->arc[4][8]=3;
    G->arc[5][2]=3;
    G->arc[5][6]=1;
    G->arc[5][9]=1;
    G->arc[6][2]=3;
    G->arc[6][3]=2;
    G->arc[6][1]=1;
    G->arc[6][5]=1;
    G->arc[6][8]=3;
    G->arc[7][3]=1;
    G->arc[7][4]=1;
    G->arc[7][8]=1;
    G->arc[7][11]=2;
    G->arc[8][7]=1;
    G->arc[8][6]=3;
    G->arc[8][4]=3;
    G->arc[8][12]=3;
    G->arc[9][2]=2;    
    G->arc[9][5]=1;
    G->arc[9][18]=2;
    G->arc[10][13]=1;
    G->arc[10][16]=2;
    G->arc[10][11]=3;
    G->arc[10][6]=2;
    G->arc[11][12]=1;
    G->arc[11][17]=1;
    G->arc[11][7]=2;
    G->arc[11][10]=3;
    G->arc[12][18]=1;
    G->arc[12][15]=1;
    G->arc[12][13]=2;
    G->arc[12][11]=1;
    G->arc[12][8]=3;
    G->arc[13][16]=1;
    G->arc[13][12]=2;
    G->arc[13][10]=1;
    G->arc[14][16]=1;
    G->arc[14][17]=3;
    G->arc[14][15]=1;
    G->arc[15][14]=1;
    G->arc[15][13]=1;
    G->arc[16][13]=1;
    G->arc[16][10]=2;
    G->arc[16][14]=1;
    G->arc[17][14]=3;
    G->arc[17][11]=1;
    G->arc[17][18]=1;
    G->arc[18][17]=1;
    G->arc[18][12]=1;
    G->arc[18][9]=2;
}

void Dijstra(PGraph G,int from,int to){
    //printf("ceshi"); 
    int i,j,index=-1;
    int n=1;//记录最短路径的个数 
    ArrayNode shortpath[Vertex];
    int flag[Vertex]={0};//标记，代表到这个顶点的距离已求出
    //初始化shortpath数组 
    for(i=0;ivertexNum;i++){
        if(from==i){
            shortpath[i].distance = 0;
            shortpath[i].path[0]=i;
            flag[from]=i; 
        }else if(G->arc[from][i]>0){
            shortpath[i].path[0]=from;
            shortpath[i].path[1]=i;
            shortpath[i].distance=G->arc[from][i];
        }else{
            shortpath[i].distance=max;
        }
    }
    //每次求出一个最短路径
    while(nvertexNum){
        index=-1;//标记点 
        for(i=0;ivertexNum;i++){
            if(i==from){
                continue;//若为自身，跳出 
            }
            if(flag[i]==0&&index==-1&&shortpath[i].distance!=max){
                index = i;
            }if(flag[i]==0&&index!=-1&&shortpath[i].distance                 index = i;//标记最短路径点 
            }
        }
        flag[index]=1;
        //修改到各个顶点的最短路径
        for(i=0;ivertexNum;i++){
            if(i==from){
                continue;
            }
            if(G->arc[index][i]>0 && G->arc[index][i]+shortpath[index].distance                 shortpath[i].distance=G->arc[index][i]+shortpath[index].distance;
                //修改路径
                j=0;
                while(1){
                    shortpath[i].path[j]=shortpath[index].path[j];
                    if(shortpath[index].path[j]==index){
                        break;
                    }
                    j++;
                }
                shortpath[i].path[j+1]=i;
            }
        } 
        n++;
    } 
    //输出from到to的最短路径及长度
    if(shortpath[to].distance==max){
        printf("%c到%c没有路径",from+'A',to+'A');
        return;
    } 
    printf("从%c到%c的最短路径是:%dn",from+'A',to+'A',shortpath[to].distance);
    printf("经过的顶点:  ");
    i=0;
    while(1){
        printf("%-3c",shortpath[to].path[i]+'A');
        if(shortpath[to].path[i]==to){
            break;
        }
        i++;
    } 
    printf("n");
}
int main(){
    Graph g;
    char from,to;
    createGraph(&g);
    scanf("%c%c",&from,&to);//输入始点与终点 
    Dijstra(&g,from-'A',to-'A');
    return 0; 
}