最小生成树+最短路径

实验8

1.最小生成树

#include<stdio.h>
#include<stdlib.h>
const int N=1010;
const int INF=1e9+7;
int n=6;
int G[N][N];
int d[N];
bool vis[N]={false};

void createjuzhen(){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            G[i][j]=INF;
        }
    }
    G[1][2]=G[2][1]=6;
    G[1][3]=G[3][1]=1;
    G[1][4]=G[4][1]=5;
    G[3][2]=G[2][3]=5;
    G[3][4]=G[4][3]=5;
    G[5][2]=G[2][5]=3;
    G[3][5]=G[5][3]=6;
    G[3][6]=G[6][3]=4;
    G[4][6]=G[6][4]=2;
    G[5][6]=G[6][5]=6;
}

int prim(int st){
    for(int i=1;i<=n;i++) d[i]=INF;
    d[st]=0;
    int ans=0;
    printf("生成最小生成树的过程：");
    for(int i=1;i<=n;i++){
        int u=-1,min=INF;
        for(int j=1;j<=n;j++){
            if(vis[j]==false&&d[j]<min){
                u=j;
                min=d[j];
            }
        }
        if(u==-1) return -1;
        vis[u]=true;
        printf(" %d",u);
        ans+=d[u];
        for(int v=1;v<=n;v++){
            if(vis[v]==false&&G[u][v]!=INF&&G[u][v]<d[v]){
                d[v]=G[u][v];
            }
        }
    }
    return ans;
}

int main(){
    //创建图的邻接矩阵
	createjuzhen();
    int ans=prim(3);
    printf("\n最小生成树边权之和：%d",ans);
}

2.最短路径问题

#include<stdio.h>
#include<stdlib.h>
#include<map>
#include<string>
#include<iostream>
using namespace std;

const int N=1010;
const int INF=1e9+7;
int n=25;
int G[N][N];
int d[N],pre[N];
bool vis[N]={false};
map<int,string> mp1;
map<string,int> mp2;

void createjuzhen(){
    //城市编号
    mp1[0]="HaErBin";
    mp1[1]="ChangChun";
    mp1[2]="ShenYang";
    mp1[3]="DaLian";
    mp1[4]="TianJin";
    mp1[5]="BeiJing";
    mp1[6]="HuHeHaoTe";
    mp1[7]="LanZhou";
    mp1[8]="XiNing";
    mp1[9]="WuLuMuQi";
    mp1[10]="XuZhou";
    mp1[11]="ZhengZhou";
    mp1[12]="XiAn";
    mp1[13]="ShangHai";
    mp1[14]="WuHan";
    mp1[15]="ChengDu";
    mp1[16]="FuZhou";
    mp1[17]="NanChang";
    mp1[18]="ZhuZhou";
    mp1[19]="GuiYang";
    mp1[20]="KunMing";
    mp1[21]="ShenZhen";
    mp1[22]="GuangZhou";
    mp1[23]="LiuZhou";
    mp1[24]="NanNing";
    mp2["HaErBin"]=0;
    mp2["ChangChun"]=1;
    mp2["ShenYang"]=2;
    mp2["DaLian"]=3;
    mp2["TianJin"]=4;
    mp2["BeiJing"]=5;
    mp2["HuHeHaoTe"]=6;
    mp2["LanZhou"]=7;
    mp2["XiNing"]=8;
    mp2["WuLuMuQi"]=9;
    mp2["XuZhou"]=10;
    mp2["ZhengZhou"]=11;
    mp2["XiAn"]=12;
    mp2["ShangHai"]=13;
    mp2["WuHan"]=14;
    mp2["ChengDu"]=15;
    mp2["FuZhou"]=16;
    mp2["NanChang"]=17;
    mp2["ZhuZhou"]=18;
    mp2["GuiYang"]=19;
    mp2["KunMing"]=20;
    mp2["ShenZhen"]=21;
    mp2["GuangZhou"]=22;
    mp2["LiuZhou"]=23;
    mp2["NanNing"]=24;
    //输出城市名称与编号
    cout<<"城市名称与其编号："<<endl;
    map<string,int>::iterator it;
    for(it=mp2.begin();it!=mp2.end();it++){
        cout<<it->first<<"  "<<it->second<<endl;
    }
    //创建邻接矩阵
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            G[i][j]=INF;
        }
    }
    G[0][1]=G[1][0]=242;
    G[1][2]=G[2][1]=305;
    G[2][3]=G[3][2]=397;
    G[2][4]=G[4][2]=704;
    G[4][5]=G[5][4]=137;
    G[5][6]=G[6][5]=668;
    G[6][7]=G[7][6]=1145;
    G[7][8]=G[8][7]=216;
    G[7][9]=G[9][7]=1892;
    G[4][10]=G[10][4]=674;
    G[5][11]=G[11][5]=695;
    G[10][11]=G[11][10]=349;
    G[11][12]=G[12][11]=511;
    G[7][12]=G[12][7]=676;
    G[10][13]=G[13][10]=651;
    G[17][13]=G[13][17]=825;
    G[11][14]=G[14][11]=534;
    G[18][14]=G[14][18]=409;
    G[12][15]=G[15][12]=842;
    G[19][15]=G[15][19]=967;
    G[20][15]=G[15][20]=1100;
    G[20][19]=G[19][20]=639;
    G[18][19]=G[19][18]=902;
    G[18][17]=G[17][18]=367;
    G[16][17]=G[17][16]=622;
    G[18][22]=G[22][18]=675;
    G[21][22]=G[22][21]=140;
    G[23][18]=G[18][23]=672;
    G[23][19]=G[19][23]=607;
    G[23][24]=G[24][23]=255;

    //输出邻接矩阵
    cout<<"邻接矩阵:"<<endl;
    for(int i=0;i<n;i++){
        cout<<mp1[i]<<"   ";
        for(int j=0;j<n;j++){
        	if(G[i][j]==INF) printf("∞  ");
            else printf("%d  ",G[i][j]);
        }
        printf("\n");
    }
}

void Dijkstra(int st){
    for(int i=0;i<n;i++){
        d[i]=INF;
        pre[i]=i;
    }
    d[st]=0;
    for(int i=0;i<n;i++){
        int u=-1,min=INF;
        for(int j=0;j<n;j++){
            if(!vis[j]&&d[j]<min){
                u=j;
                min=d[j];
            }
        }
        if(u==-1) return ;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(!vis[v]&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
                d[v]=G[u][v];
                pre[v]=u;
            }
        }     
    }
}

void DFS(int s,int v){
    if(s==v){
        cout<<mp1[s];
        return ;
    }
    DFS(s,pre[v]);
    cout<<" -> "<<mp1[v];
}

int main(){
    //创建图的邻接矩阵
	createjuzhen();
    Dijkstra(mp2["ZhengZhou"]);
    printf("请输入终点城市：\n");
    string str;
    //scanf("%s",str);
    cin>>str;
    cout<<"最短距离："<<d[mp2[str]]<<endl;
    cout<<"最短路径：";
    DFS(11,mp2[str]);
}