tudezuiduanlujin.txt

来自「这个程序是关于图的最短路径的 对于需要这个程序的朋友们快来试试吧」· 文本 代码 · 共 101 行

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY    0
#define MAX_VERTEX_NUM 20
#define MAX_SIZE 10000
typedef enum {DG,DN,UDG,UDN}  GraphKind;
typedef struct ArcCell{
    int adj;
    char * info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
    int vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
    GraphKind kind;
}MGraph;
//-------
int LocateVex(int vexs[],int v){               //确定节点v在节点向量中的位置
    for(int i=0;i<MAX_VERTEX_NUM;i++)
        if(vexs[i]==v)
            return i;
        printf("不存在这个节点!");
        exit(0);
}
bool CreateD(MGraph &G){
    int IncInfo,v1,v2,w,i,j,k;
    printf("请输入有向图的顶点数和弧数，以及各弧是否含有其他信息(0表示不含其它信息)\n");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
    for(i=0;i<G.vexnum;i++)                                            //初始化节点向量
        G.vexs[i]=i+1;  
    for(i=0;i<G.vexnum;i++){                                             //初始化邻接矩阵
        for(j=0;j<G.vexnum;j++){
            G.arcs[i][j].adj=INFINITY;    G.arcs[i][j].info=NULL;
        }
    }
    for(k=0;k<G.arcnum;k++){                                            //输入一条边及依附的定点及权值
        printf("请输入第%d弧的两个节点及权值:",k+1);
        scanf("%d%d%d",&v1,&v2,&w);
        i=LocateVex(G.vexs,v1);           j=LocateVex(G.vexs,v2);        //找到两个顶点在邻接矩阵中的位置
        G.arcs[i][j].adj=w;
        if(IncInfo)
            scanf("%s",G.arcs[i][j].info);                        //若弧含有相关信息，则输入信息
    }
    return true;
}
//---------------------------------------------------
bool final[MAX_VERTEX_NUM]={false};     //用于标记到顶点i的最短路径是否已经找到 
bool P[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int D[MAX_VERTEX_NUM]={0};
void ShortestPath_DIJ(MGraph G,int v0){
    int i,w,v;
    for(v=0;v<G.vexnum;v++){
        D[v]=G.arcs[v0][v].adj;
        for(w=0;w<G.vexnum;w++)
            P[v][w]=false;
        if(D[v]<MAX_SIZE){
            P[v][v0]=true;    P[v][v]=true;
        }
    }
    D[v0]=0;    final[v0]=true;
    for(i=1;i<G.vexnum;i++){
        int min=MAX_SIZE;
        for(w=0;w<G.vexnum;w++)
            if(!final[w])
                if(D[w]<min){
                    min=D[w];    v=w;
                }
                final[v]=true;
                for(w=0;w<G.vexnum;w++)
                    if(!final[w]&&(min+G.arcs[v][w].adj<D[w])){
                        D[w]=min+G.arcs[v][w].adj;
                        for(i=0;i<G.vexnum;i++)
                            P[w][i]=P[v][i];
                        P[w][w]=true;
                    }
    }
}
int main(){
    
    
    MGraph G;
    CreateD(G);
    int v0;
    printf("请输入始点:");
    scanf("%d",&v0);
    ShortestPath_DIJ(G,v0-1);
    for(int i=0;i<G.vexnum;i++){
        if(i!=v0-1){
            printf("V%d to V%d is:",v0,i+1);
            printf("<");
            for(int j=0;j<G.vexnum;j++)
                if(P[i][j]&&j!=i)
                    printf("V%d,",j+1);
                printf("V%d>",i+1);
                printf("--Length is:%d\n",D[i]);
        }
    }
    return 0;
}