编辑代码

#include <iostream>
#include <queue>
using namespace std;

#define ding 6;
#define bian 10;

#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;

char vex[6] = {'1','2','3','4','5','6'};
char arc[100][2] = {{'1','2'},{'1','3'},{'1','4'},{'2','3'},{'2','5'},{'3','4'},{'3','5'},{'3','6'},{'4','6'},{'5','6'}};
int w[10]={6,1,5,5,3,5,6,4,2,6};
bool visited[5];
bool s[5];
int d[5];
int path[5];
int Vexset[5];
int D[5][5];
int Path[5][5];
typedef struct{
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum,arcnum;
}AMGraph;


struct{
    VerTexType adjvex;
    ArcType lowcost;
}closedge[MVNum];

struct{
    VerTexType Head;
    VerTexType Tail;
    ArcType lowcost;
}Edge[21];

void sort(){
    int flag;
    for(int i=0;i<20;i++){
        flag = 0;
        for(int j=1;j<20;j++){
            if(Edge[j-1].lowcost>Edge[j].lowcost){
                flag=1;
                Edge[20] = Edge[j];
                Edge[j] = Edge[j-1];
                Edge[j-1] = Edge[20];
            }
        }
    }
    //for(int i=0;i<20;i++)
        //cout<<Edge[i].Head<<Edge[i].lowcost<<endl;
}

int LocateVex(AMGraph G,char v){
    for(int i = 0;i<G.vexnum;i++){
        if(G.vexs[i]==v)    
            return i;
    }
    return 0;
}
bool CreateUDN(AMGraph &G){
    //cin>>G.vexnum>>G.arcnum;
    int e=0;
    G.vexnum = ding;
    G.arcnum = bian;
    for(int i = 0;i<G.vexnum;i++)
        G.vexs[i] = vex[i];//cin>>G.vexs[i];
    for(int i = 0;i<G.vexnum;i++)
        for(int j = 0;j<G.vexnum;j++)
            G.arcs[i][j] = MaxInt;
    for(int k = 0;k<G.arcnum;k++){
        char v1,v2;
        int i,j;
        //int w=1;
        v1 = arc[k][0];
        v2 = arc[k][1];//cin>>v1>>v2>>w;
        i = LocateVex(G,v1);
        j = LocateVex(G,v2);
        G.arcs[i][j] = w[k];
        //
        Edge[e].Head = v1;
        //cout<<i<<Edge[e].Head;
        Edge[e].Tail = v2;
        Edge[e++].lowcost = w[k];
        G.arcs[j][i] = G.arcs[i][j];
        Edge[e].Head = v2;
        Edge[e].Tail = v1;
        Edge[e++].lowcost=G.arcs[i][j];
    }
    return true;
}
void DFS(AMGraph G,int v){
    cout<<G.vexs[v];
    visited[v] = true;
    for(int w = 0;w<G.vexnum;w++)
        if(G.arcs[v][w]!=0 && !(visited[w]))
            DFS(G,w);
}
void DFSTraverse(AMGraph G){
    for(int v=0;v<G.vexnum;v++)
        visited[v] = false;
    for(int v=0;v<G.vexnum;v++)
        if(!visited[v])  DFS(G,v);
}
void BFS(AMGraph G,int v){
    queue <int> q;
    cout<<G.vexs[v];
    visited[v] = true;
    q.push(v);
    while(!q.empty()){
        int u;
        u = q.front();
        q.pop();
        for(int w=0;w<G.vexnum;w++)
            if(G.arcs[u][w]!=0 && !(visited[w])){
                cout<<G.vexs[w];
                visited[w] = true;
                q.push(w);
            }
    }
}
void BFSTraverse(AMGraph G){
    for(int v=0;v<G.vexnum;v++)
        visited[v] = false;
    for(int v=0;v<G.vexnum;v++)
        if(!visited[v]) BFS(G,v);
}
//普里姆
void MninSpanTree_Prim(AMGraph G,VerTexType u){
    int k = LocateVex(G,u);
    int k1;
    for(int j=0;j<G.vexnum;j++)
        if(j!=k)    closedge[j] = {u,G.arcs[k][j]};
    closedge[k].lowcost = 0;
    for(int i=1;i<G.vexnum;i++){
        int min = MaxInt;
        for(int j=0;j<G.vexnum;j++)
            if(closedge[j].lowcost<min&&closedge[j].lowcost!=0){
                k1 = j;
                min = closedge[j].lowcost;
            }   
        k =k1;
        VerTexType u0,v0;
        u0 = closedge[k].adjvex;
        v0 = G.vexs[k];
        //for(int c = 0;c<G.vexnum;c++){
        //    cout<<closedge[c].adjvex<<closedge[c].lowcost<<". ";
        //}
        //cout<<endl<<k;
        //cout<<endl;
        cout<<u0<<v0<<endl;
        closedge[k].lowcost = 0;
        for(int j=0;j<G.vexnum;j++)
            if(G.arcs[k][j]<closedge[j].lowcost)
                closedge[j] = {G.vexs[k],G.arcs[k][j]};
    } 
}
// 克鲁斯卡尔
void MiniSpanTree_Kruskal(AMGraph G){
    sort();
    for(int i=0;i<G.vexnum;i++)
        Vexset[i] = i;
    for(int i=0;i<G.arcnum*2;i++){
        int v1,v2,vs1,vs2;
        v1 = LocateVex(G,Edge[i].Head);
        v2 = LocateVex(G,Edge[i].Tail);
        vs1 = Vexset[v1];
        vs2 = Vexset[v2];
        if(vs1!=vs2){
            cout<<Edge[i].Head<<Edge[i].Tail<<endl;
            for(int j=0;j<G.vexnum;j++)
                if(Vexset[j]==vs2)  Vexset[j] = vs1;
        }
    }        
}
//迪杰斯特拉
void ShortestPath_DIJ(AMGraph G,int v0){
    int n = G.vexnum;
    for(int v=0;v<n;v++){
        s[v] = false;
        d[v] = G.arcs[v0][v];
        if(d[v]<MaxInt) path[v] = v0;
        else path[v] = -1;
    }
    s[v0] = true;
    d[v0] = 0;
    int v;
    for(int i=1;i<n;i++){
        int min = MaxInt;
        for(int w=0;w<n;w++)
            if(!s[w]&&d[w]<min)
                {v = w;min=d[w];}
            s[v] = true;
        for(int w=0;w<n;++w)
            if(!s[w]&&(d[v]+G.arcs[v][w]<d[w]))
            {
                d[w] = d[v] + G.arcs[v][w];
                path[w] = v;
            }
    }
    for(int i=0;i<n;i++)
        cout<<d[i]<<endl;
}
int main() {
    AMGraph G;
    CreateUDN(G);
    //DFSTraverse(G);
    //BFSTraverse(G);
    //MninSpanTree_Prim(G,'1');
    //MiniSpanTree_Kruskal(G);
    ShortestPath_DIJ(G,0);
    //cout<<G.arcnum<<endl;
    for(int i =0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            if(G.arcs[i][j]==MaxInt)    cout<<0;
            else    cout<<G.arcs[i][j];
        }
        cout<<endl;
    }
	return 0;
}