²      问题描述

#include <stdio.h>
#include <stdlib.h>

#include<stdio.h>
#include<stdlib.h>

交通网络中常常提出这样的问题:两地之间是否有路相通?在有多条通路的情况下,哪一条最短?以上问题就是带权图中求最短路径的问题。

#define MVnum 100   //最大顶点数
#define Maxint 32767 //定义计算机中的int的最大值

#define MaxSize 100
#define ApplySpaceFail -1
#define TRUE  1
#define FALSE 0
#define    UNLIMIT 65535
#define Edges 15

²      基本要求

typedef enum {FALSE,TRUE} boolean;
typedef struct  
{//建立图的存储结构
    char vexs[MVnum];    
//顶点数组
    int
arcs[MVnum][MVnum];   //邻接矩阵
}MGraph;

int visited[MaxSize];
int P[MaxSize];
int D[MaxSize];
int PF[MaxSize][MaxSize];
int DF[MaxSize][MaxSize];

⑴用Dijkstra算法求最短路径,图中的顶点数n不得少于10个。

int D1[MVnum],P1[MVnum];
int D[MVnum][MVnum];
int P[MVnum][MVnum];

typedef struct Graph{
    char vex[MaxSize];
    int  GraMtr[MaxSize][MaxSize];
    int  numVex,numEdge;
}GraNode;

⑵用户输入源点和目标点后,程序应输出源点到目标点的最短路径,并计算出途中所需时间或花费的交通费用。

void createMGraph(MGraph *G,int n,int e);
void Dijkstra(MGraph G,int v1,int n);
void Floyd(MGraph G,int n);

typedef struct Gra{
    int begin;
    int end;
    int weight;
}GraStr[Edges],GraS;

源程序:

int main()
{
    MGraph G;
    int n,e,v,w,k;
    int xz = 1;
    printf(“请输入图中顶点个数和边数n,e: “);
    scanf(“%d,%d”,&n,&e);
    createMGraph(&G,n,e);
    while(xz != 0)
    {
        printf(“n”);
        printf(“******求城市之间的最短路径******n”);
        printf(“================================n”);
        printf(“1.求一个城市到所有城市的最短路径n”);
        printf(“2.求任意的两个城市之间的最短路径n”);
        printf(“================================n”);
        printf(” 请选择: 1 或 2,选择 0 退出 :   “);
        scanf(“%d”,&xz);
        
        if(xz == 2)
        {
            Floyd(G,n);   //调用佛洛依德算法
            printf(“请输入源点(起点)和终点: v,w: “);
            scanf(“%d,%d”,&v,&w);
            k = P[v][w];
            if(k == 0)
            printf(“顶点%d到%d没有路径!nn”,v,w);
            else
            {
                printf(“从顶点%d到%d的最短路径是:%d”,v,w,v);
             while(k != w)
             {
                 printf(“->%d”,k); //输出后继顶点
                 k = P[k][w];      //继续寻找下一个后继顶点
             }
             printf(“->%dn”,w);  //输出终点w

void CreatGraph(GraNode *G){
    int i,j;
    
    if(G==NULL){
        printf(“申请空间失败!n”);
        exit(ApplySpaceFail);
    }    
    G->numVex=9;    
    G->numEdge=15;
    for(i=0;i<G->numVex;i++){
        for(j=0;j<G->numVex;j++)
                    G->GraMtr[i][j]=UNLIMIT;
    }
    for(i=0;i<G->numVex;i++){
        scanf(“%c”,&G->vex[i]);
    }
    G->GraMtr[0][1]=G->GraMtr[1][0]=10;//1;
    G->GraMtr[0][5]=G->GraMtr[5][0]=11;//1;
    G->GraMtr[1][2]=G->GraMtr[2][1]=18;//1;
    G->GraMtr[1][6]=G->GraMtr[6][1]=16;//1;
    G->GraMtr[1][8]=G->GraMtr[8][1]=12;//1;
    G->GraMtr[2][3]=G->GraMtr[3][2]=22;//1;
    G->GraMtr[2][8]=G->GraMtr[8][2]=8;//1;
    G->GraMtr[3][4]=G->GraMtr[4][3]=20;//1;
    G->GraMtr[3][6]=G->GraMtr[6][3]=24;//1;
    G->GraMtr[3][7]=G->GraMtr[7][3]=16;//1;
    G->GraMtr[3][8]=G->GraMtr[8][3]=21;//1;
    G->GraMtr[4][5]=G->GraMtr[5][4]=26;//1;
    G->GraMtr[4][7]=G->GraMtr[7][4]=7;//1;
    G->GraMtr[5][6]=G->GraMtr[6][5]=17;//1;
    G->GraMtr[6][7]=G->GraMtr[7][6]=19;//1;
    /*G->GraMtr[0][1]=G->GraMtr[1][0]=1;
    G->GraMtr[0][2]=G->GraMtr[2][0]=5;
    G->GraMtr[1][2]=G->GraMtr[2][1]=3;
    G->GraMtr[1][3]=G->GraMtr[3][1]=7;
    G->GraMtr[1][4]=G->GraMtr[4][1]=5;
    G->GraMtr[4][3]=G->GraMtr[3][4]=2;
    G->GraMtr[2][4]=G->GraMtr[4][2]=1;
    G->GraMtr[2][5]=G->GraMtr[5][2]=7;
    G->GraMtr[4][5]=G->GraMtr[5][4]=3;
    G->GraMtr[3][6]=G->GraMtr[6][3]=3;
    G->GraMtr[4][6]=G->GraMtr[6][4]=6;
    G->GraMtr[4][7]=G->GraMtr[7][4]=9;
    G->GraMtr[5][7]=G->GraMtr[7][5]=5;
    G->GraMtr[8][6]=G->GraMtr[6][8]=7;
    G->GraMtr[6][7]=G->GraMtr[7][6]=2;
    G->GraMtr[8][7]=G->GraMtr[7][8]=4;*/
}

#include
<stdio.h>
#include <stdlib.h>
#define INFINITY 32767
#define MaxVertexNum 30
typedef char VertexType;
typedef int EdgeType;
typedef struct{
   VertexType vexs[MaxVertexNum];
   EdgeType edges[MaxVertexNum][MaxVertexNum];
   int n,e;
}MGraph;

             printf(”  路径长度: %dnn”,D[v][w]);
              }
            }
            else
            if(xz == 1)
            {
                printf(“求单源路径,请输入源点 v :”);
                scanf(“%d”,&v);
                printf(“n”);
                Dijkstra(G,v,n); //调用Dijkstra算法
            }
        }
        printf(“n”);
        printf(“结束!谢谢使用!n”);
        return 0;
        }

void MAINDFS_TravelGraph(GraNode
*G,int i){
    int k;
    printf(“%c”,G->vex[i]);
    visited[i]=TRUE;
    for(k=i+1;k<G->numVex;k++)
        if(G->GraMtr[i][k]==1&&visited[k]!=TRUE){
            MAINDFS_TravelGraph(G,k);
        }
    
}

typedef
enum{
   FALSE,TRUE
}Boolean;

void createMGraph(MGraph *G,int n,int e)
{
//采用邻接矩阵构建有向图,n表示定点数,e表示变数

void DFS_TravelGraph(GraNode
*G){
    int i;
    for(i=0;i<MaxSize;i++){
        visited[i]=FALSE;
    }
    for(i=0;i<G->numVex;i++){
        if(visited[i]==FALSE)MAINDFS_TravelGraph(G,i);    
    }
}

void
CreateMGraph(MGraph *G)
{
 int i,j,k,w;
 printf(“nEnter n & e:n”);
 scanf(“%d%d”,&G->n,&G->e);
 for (i=0;i<G->n;i++)
    for (j=0;j<G->n;j++)
       G->edges[i][j]=INFINITY;
 printf(“Enter edge(i & j)& weight:n”);
 for (k=0;k<G->e;k++)
    {
     scanf(“%d%d%d”,&i,&j,&w);
     G->edges[i][j]=w;
    }
}
void Dijkstra(MGraph *G,long D[],int P[],int s)
{
 int i,j,k,min;
 Boolean S[MaxVertexNum];
 for(i=0;i<G->n;i++)
  {
   S[i]=FALSE;
   D[i]=G->edges[s][i];
   if(D[i]<INFINITY)
      P[i]=s;
   else
      P[i]=-1;
  }
 S[s]=TRUE;
 D[s]=0;
 for(i=0;i<G->n-1;i++)
  {
   min=INFINITY;
   for(j=0;j<G->n;j++)
      if(!S[j]&&D[j]<min)
        {
         min=D[j];
         k=j;
        }
   if(min==INFINITY)
      return;
   S[k]=TRUE;
   for(j=0;j<G->n;j++)
      if(!S[j]&&(D[j]>D[k]+G->edges[k][j]))
        {
         D[j]=D[k]+G->edges[k][j];
         P[j]=k;
        }
  }
}
void Print(MGraph *G,int P[],long D[],int t)
{
 int i=0,pre,a[MaxVertexNum];
 long k=32767;
 if(D[t]==k)
   {
    printf(“no way!n”);
    return;
   }
 printf(“Distance:%ld,Path:”,D[t]);
 a[i]=t;
 pre=P[t];
 while(pre!=-1)
  {
   a[++i]=pre;
   pre=P[pre];
  }
 for(;i>=0;i–)
   printf(“%d  “,a[i]);
}
void main()
{
 void CreateMGraph(MGraph *G);
 void Dijkstra(MGraph *G,long D[],int P[],int s);
 void Print(MGraph *G,int P[],long D[],int t);
 long int D[MaxVertexNum];
 int P[MaxVertexNum],s,t,l=1,k=1;
 MGraph *G;
 CreateMGraph(G);
 do
  {
   printf(“n*****please make a choice*****n”);
   printf(“1.searchn0.EXITn”);
  
printf(“******************************n”);
   scanf(“%d”,&l);
   switch(l)
    {
     case 0:k=0;break;
     case 1:
            if(l==1)
             {
              printf(“shu ru yuan dian & zhong dian:n”);
              scanf(“%d%d”,&s,&t);
             }
            Dijkstra(G,D,P,s);
            Print(G,P,D,t);
            break;
    }
  }while(k);
}

    int i,j,k,w;
    for(i = 1;i < n;i ++)
    G -> vexs[i] = (char)i;
    for(i = 1;i < n + 1;i ++)
    for(j = 1;j < n + 1;j ++)
    {
        G -> arcs[i][j] = Maxint;   //初始化邻接矩阵
    }
    printf(“输入%d条边的i,j及w:nn”,e);
    for(k = 1;k < e + 1;k ++)
    {
        scanf(“%d,%d,%d”,&i,&j,&w);
        G -> arcs[i][j] = w;
    }
    printf(“有向图的存储结构构建完毕!nn”);
    
}

void  BFS_TravelGraph(GraNode
*G){
    int Qu[MaxSize];
    int front,rear;
    front=rear=0;
    int i,t;
    for(i=0;i<G->numVex;i++){
        visited[i]=FALSE;
    }
    rear++;
    Qu[rear]=0;
    printf(“%c”,G->vex[0]);
    visited[0]=TRUE;
    while(front!=rear){
        front=(front+1)%MaxSize;
        t=Qu[front];
        for(i=0;i<G->numVex;i++){
            if(visited[i]==FALSE&&G->GraMtr[t][i]==1){
                rear++;
                Qu[rear]=i;
                printf(“%c”,G->vex[i]);
                visited[i]=TRUE;
            }
        }
    }
}    

void Dijkstra(MGraph G,int v1,int n)
{
    int D2[MVnum];
    int P2[MVnum];
    int v,i,w,min;
    boolean S[MVnum];
    for(v = 1;v < n + 1;v ++)
    {
        S[v] = FALSE;;     //置空最短路径终点集
        D2[v] = G.arcs[v1][v];
        if(D2[v] < Maxint)
        P2[v] = v1;        //v1是v的前驱
        else
        P2[v] = 0;         //v没有前驱

void MiniSpanTree_Prim(GraNode
*G){
    int i,j,k,min;
    int adjvex[MaxSize]; //相关顶点数组
    int
lowcost[MaxSize];//相关顶点权值
    adjvex[0]=0;
    lowcost[0]=0;
    for(i=1;i<G->numVex;i++){
        adjvex[i]=0;
        lowcost[i]=G->GraMtr[0][i];
    }
    for(i=1;i<G->numVex;i++){
        min=UNLIMIT;
        for(j=0;j<G->numVex;j++){
            if(lowcost[j]!=0&&lowcost[j]<min){
                min=lowcost[j];
                k=j;
            }
        }
        printf(” (%d,%d) “,adjvex[k],k);
        lowcost[k]=0;
        for(j=0;j<G->numVex;j++){
            if(lowcost[j]!=0&&G->GraMtr[k][j]<lowcost[j]){
                lowcost[j]=G->GraMtr[k][j];
                adjvex[j]=k;
            
            }
        }
    }
}

    }
    
    D2[v1] = 0;         //s集初始时只有源点,源点到源点的距离为0

void CreatGraStr(GraStr Gs){
    Gs[0].begin=0;Gs[0].end=1;Gs[0].weight=10;
    Gs[1].begin=0;Gs[1].end=5;Gs[1].weight=11;
    Gs[2].begin=1;Gs[2].end=2;Gs[2].weight=18;
    Gs[3].begin=1;Gs[3].end=6;Gs[3].weight=16;
    Gs[4].begin=1;Gs[4].end=8;Gs[4].weight=12;
    Gs[5].begin=2;Gs[5].end=3;Gs[5].weight=22;
    Gs[6].begin=2;Gs[6].end=8;Gs[6].weight=8;
    Gs[7].begin=3;Gs[7].end=4;Gs[7].weight=20;
    Gs[8].begin=3;Gs[8].end=6;Gs[8].weight=24;
    Gs[9].begin=3;Gs[9].end=7;Gs[9].weight=16;
    Gs[10].begin=3;Gs[10].end=8;Gs[10].weight=21;
    Gs[11].begin=4;Gs[11].end=5;Gs[11].weight=26;
    Gs[12].begin=4;Gs[12].end=7;Gs[12].weight=7;
    Gs[13].begin=5;Gs[13].end=6;Gs[13].weight=17;
    Gs[14].begin=6;Gs[14].end=7;Gs[14].weight=19;
}

    S[v1] = TRUE;
    
    for(i = 2;i < n;i ++)
    {
    min = Maxint;
    for(w = 1;w < n + 1;w ++)
    if(!S[w] && D2[w] <
min)
    {
        v = w;
        min = D2[w];
    }
    S[v] = TRUE;
    for(w = 1;w < n + 1;w ++)
    {
        if(!S[w] && (D2[v] +
G.arcs[v][w] < D2[w]))
        {
            D2[w] = D2[v] + G.arcs[v][w];
            P2[w] = v;
        }
    }
        printf(“路径长度     路径n”);
        
        for(i = 1;i < n + 1;i ++)
        {
            printf(“%9d”,D2[i]);
            printf(“%9d”,i);
            v = P2[i];
            while(v != 0)
            {
                printf(“<-%d”,v);
                v = P2[v];
            }
            printf(“n”);
        }
}
}

void AddQuList(GraStr Gs){
    int i,j;
    GraS t;
    for(i=0;i<Edges-1;i++){
        for(j=0;j<Edges-i-1;j++){
            if(Gs[j].weight>Gs[j+1].weight){
                t=Gs[j];        
                Gs[j]=Gs[j+1];
                Gs[j+1]=t;
            }
        }
    }
}

void Floyd(MGraph G,int n)
{
    //int n;
    int i;
    int j;
    int k;
    for(i = 1;i < n + 1;i ++)
    for(j = 1;j < n + 1;j ++)
    {
        if(G.arcs[i][j] !=
Maxint)
        P[i][j] = j;
        else
        P[i][j] = 0;
        D[i][j] = G.arcs[i][j];
    }
    
    for(k = 1;k < n + 1;k ++)
    {
        for(i = 1;i < n + 1;i ++)
        for(j = 1;j < n + 1;j ++)
        {
            if(D[i][k] +
D[k][j] < D[i][j])
            {
                D[i][j] = D[i][k] + D[k][j];
                P[i][j] = P[i][k];
            }
        }
    }
}

int Find(int *parent,int f){
    while(parent[f]>0)
        f=parent[f];
    return f;

}
        
void MiniSpanTree_Kruscal(GraStr
Gs){
    int parent[Edges];    
    int i,m,n;
    for(i=0;i<Edges;i++){
        parent[i]=0;    
    }
    for(i=0;i<Edges;i++){
        m=Find(parent,Gs[i].begin);
        n=Find(parent,Gs[i].end);
        if(n!=m){
            parent[m]=n;
            printf(“(%d,%d) weight:%d”,Gs[i].begin,Gs[i].end,Gs[i].weight);printf(“n”);
        }
    }
}
    
void ShortPath_Dijstra(GraNode
*G){
    int i,j,k,min;
    int final[MaxSize];
    for(i=0;i<G->numVex;i++){
        final[i]=0;
        P[i]=0;
        D[i]=G->GraMtr[0][i];
    }
    final[0]=1;
    D[0]=0;
    for(i=1;i<G->numVex;i++){
        min=UNLIMIT;    
        for(j=0;j<G->numVex;j++){
            if(final[j]!=1&&D[j]<min){
                min=D[j];
                k=j;
            }
        }
        final[k]=1;
        for(j=0;j<G->numVex;j++){
            if(final[j]!=1&&min+G->GraMtr[k][j]<D[j]){
                D[j]=min+G->GraMtr[k][j];
                P[j]=k;
            }
        }
    }
}
        
void Dijstra_DisplayPath(GraNode
*G){
    int w,k;
    int v=0;
    for(w=v+1;w<G->numVex;w++){
        printf(“v%d-v%d  weight:%d   “,v,w,D[w]);
        k=P[w];
        printf(“%d->”,w);
        while(k!=v){
            printf(“%d->”,k);
            k=P[k];
        }
        printf(“%d”,v);
        printf(“n”);
    }
}

void ShortPath_Floyd(GraNode
*G){
    int v,k,w;
    for(v=0;v<G->numVex;v++){
        for(w=0;w<G->numVex;w++){
            PF[v][w]=w;
            DF[v][w]=G->GraMtr[v][w];
        }
    }
    for(k=0;k<G->numVex;k++){
        for(v=0;v<G->numVex;v++){
            for(w=0;w<G->numVex;w++){
                if(DF[v][k]+DF[k][w]<DF[v][w]){
                    DF[v][w]=DF[v][k]+DF[k][w];
                    PF[v][w]=PF[v][k];
                }
            }
        }
    }
}    

void Floyd_DisplayPath(GraNode
*G){
    int v,w,k;
    for(v=0;v<G->numVex;v++){
        for(w=v+1;w<G->numVex;w++){
            printf(“v%d-v%d   weight: %d “,v,w,DF[v][w]);        
            k=PF[v][w];
            printf(“%d”,v);
            while(k!=w){
                printf(“->%d”,k);
                k=PF[k][w];
            }
            printf(“->%d”,w);
            printf(“n”);
        }
    printf(“n”);        
    }
}    

int main(void){
    GraNode *Gp;
    Gp=(GraNode *)malloc(sizeof(GraNode));
    CreatGraph(Gp);
    //图的遍历(深度遍历广度遍历)
    //printf(“深度遍历:”);DFS_TravelGraph(Gp);printf(“n”);
    //printf(“广度遍历:”);BFS_TravelGraph(Gp);printf(“n”);
    //最小生成树(普里姆算法克鲁斯卡尔算法)
    printf(”    普里姆算法:”);MiniSpanTree_Prim(Gp);printf(“n”);
    GraStr GS;CreatGraStr(GS);
    AddQuList(GS);printf(“克鲁斯卡尔算法:”);printf(“n”);
    MiniSpanTree_Kruscal(GS);printf(“n”);
    //最短路径(迪杰斯特拉算法弗洛依德算法)
    printf(“迪杰斯特拉算法:”);printf(“n”);
    ShortPath_Dijstra(Gp);Dijstra_DisplayPath(Gp);
    printf(“弗洛依德算法:”);printf(“n”);
    ShortPath_Floyd(Gp);Floyd_DisplayPath(Gp);
    return 0;
}