PATIR 2016-12-24 06:20 采纳率: 0%
浏览 1619

最短路径问题,迪杰斯特拉算法

 #include<iostream>
#include<iomanip>
using namespace std;
#define MAXINT      10000       /*无穷大*/
#define MVNUM      40
#define MAX 40

typedef struct
{
    char *name;
    int num;
    char *introduction;
}INFORMATION;

typedef struct ACCESS
{
    int length;
}ACCESS,LENGTHA[MVNUM][MVNUM];

typedef struct
{
    INFORMATION VEXS[MVNUM];
    LENGTHA ARCS;// Maybe error
    int VEXNUM,ARCNUM;
}AMGRAPH;

AMGRAPH A;//全局变量

AMGRAPH CreatGraph()   //初始化
{
    AMGRAPH G;
    int i, j;
    G.VEXNUM = 12;   //14个顶点
    G.ARCNUM = 16;   //14条弧
    for (i = 0; i<G.VEXNUM; i++)
        G.VEXS[i].num = i;    //第i个景点的编号为i

    G.VEXS[0].name="26栋宿舍";
    G.VEXS[1].name="二饭";
    G.VEXS[2].name="泳池";
    G.VEXS[3].name="网球场";
    G.VEXS[4].name="沙地";
    G.VEXS[5].name="旧场";
    G.VEXS[6].name="新场";
    G.VEXS[7].name="明德楼";
    G.VEXS[8].name="图书馆";
    G.VEXS[9].name="弘毅楼";
    G.VEXS[10].name="天佑楼";
    G.VEXS[11].name="艺悦楼";

    G.VEXS[0].introduction="26栋宿舍位于学子路西侧,是计算机学院学生所住宿舍,万通超市上方。";
    G.VEXS[1].introduction="第二学生饭堂位于学子路东侧,是学生好评最多的食堂。";
    G.VEXS[2].introduction="北理工泳池位于学校后山半山腰上,对学生及社会人士都开放。";
    G.VEXS[3].introduction="网球场位于学校东门附近,有4个场地供学生打网球。";
    G.VEXS[4].introduction="沙地位于网球场西侧,以往学生在此举办各种活动,是一处聚会场地。";
    G.VEXS[5].introduction="旧场位于网球场北侧,是北理珠最早的篮球场。";
    G.VEXS[6].introduction="新场位于沙地西侧,是较新的篮球场。";
    G.VEXS[7].introduction="明德楼位于学校中部,在夺命坡上方,是主要教学楼之一。";
    G.VEXS[8].introduction="图书馆位于学校北门一侧,集图书馆、办公室、酒店于一体。";
    G.VEXS[9].introduction="弘毅楼位于学校新大门对面,是主要教学楼之一。";
    G.VEXS[10].introduction="天佑楼位于弘毅楼西侧,是航空学院的主教学楼。";
    G.VEXS[11].introduction="艺悦楼位于天佑楼西侧,是设计与艺术学院的主教学楼。";

    for (i = 0; i<G.VEXNUM; i++)
    for (j = 0; j<G.VEXNUM; j++)
        G.ARCS[i][j].length = MAXINT;

    G.ARCS[0][1].length=20;
    G.ARCS[0][2].length=100;
    G.ARCS[0][3].length=280;
    G.ARCS[1][3].length=280;
    G.ARCS[1][4].length=110;
    G.ARCS[1][7].length=210;
    G.ARCS[2][7].length=130;
    G.ARCS[1][9].length=280;
    G.ARCS[3][4].length=20;
    G.ARCS[3][5].length=5;
    G.ARCS[4][6].length=5;
    G.ARCS[5][8].length=35;
    G.ARCS[6][8].length=50;
    G.ARCS[7][9].length=80;
    G.ARCS[8][9].length=200;
    G.ARCS[9][10].length=40;
    G.ARCS[10][11].length=20;

    for (i=0;i<G.VEXNUM;i++)
    for (j=0;j<G.VEXNUM;j++)
        G.ARCS[j][i].length = G.ARCS[i][j].length;  //无向网
    return G;
}

void SHORTESTPATH_DIJ(AMGRAPH *G)
{//DIJ算法,计算最短路径
    int V,min,i,j,w,k=0,V0,f=1,t;
    int D[32],PATH[32][32];
    bool S[32];

    while (f)
    {
        cout<<"请输入一个起始景点编号:";
        cin>>V0;   //输入一个值赋给V0
        if (V0<0 || V0>G->VEXNUM)
        {
            cout<<"景点编号不存在!请重新输入景点编号:";
            cin>>V0;
        }
        if (V0 >=0 && V0<G->VEXNUM)
            f=0;
    }

    for(V=0;V<G->VEXNUM;V++)
    {
        S[V]=false;
        D[V]=G->ARCS[V0][V].length;
        for(w=0;w<G->VEXNUM;w++)
        {
            PATH[V][w]=0;
        }
        if(D[V]<MAXINT) 
        {
            PATH[V][V0]=1;
            PATH[V][V]=1;
        }
    }

    D[V0]=0;
    S[V0]=true;

    for(i=1;i<G->VEXNUM;i++) 
    {
        min=MAXINT;
        for(w=0;w<G->VEXNUM;w++)
        {
            if(!S[w]&&D[w]<min)
            {
                V=w;
                min=D[w];
            }
        }
        S[V]=true;

        for(w=0;w<G->VEXNUM;w++)
        {
            if(!S[w] && (min+G->ARCS[V][w].length<D[w]))
            {
                D[w]=min+G->ARCS[V][w].length;
                for(j=0;j<G->VEXNUM;j++)
                PATH[w][j]=PATH[V][j];

                PATH[w][w]=1;
            }
        }
    }


    for(V=0;V<G->VEXNUM;V++)
        {
        t=0;
            if(V0!=V)
                printf("%s",G->VEXS[V0].name);
        for(w=0;w<G->VEXNUM;w++)
            {
                if(PATH[V][w]!=0 && w!=V0)
                {
                    printf("-%s",G->VEXS[w].name);
                    if(w==5||w==6)
                    {
                        t=1;
                    }
                }
                k++;
            }

        if(V0!=V&&(V0==5||V0==6||t==1))
        {
             cout<<"\t此路段部分需步行!";
             t=0;
        }

        if(k>G->VEXNUM-1 && V0!=V)
        printf("\t路程:%dm\n\n",D[V]);

        }

}

void SHORTESTPATH_FLOYD(AMGRAPH G)
{//FLOYD算法计算各对顶点之间的最短路径
    int D[32][32],PATH[32][32];
    int i,j,k;

    for(i=0;i<G.VEXNUM;i++)
        for(j=0;j<G.VEXNUM;i++)
    {
        D[i][j]=G.ARCS[i][j].length;
        if(D[i][j]<MAXINT) PATH[i][j]=i;
        else PATH[i][j]=-1;
    }

    for(k=0;k<G.VEXNUM;k++)
        for(i=0;i<G.VEXNUM;i++)
            for(j=0;j<G.VEXNUM;j++)
            {
                if(D[i][k]+D[k][j]<D[i][j])
                {
                    D[i][j]=D[i][k]+D[k][j];
                    PATH[i][j]=PATH[k][j];
                }
            }
}


void printjuzhen(AMGRAPH G)
{
    int i,j,W=0;
    cout<<"图的邻接矩阵:"<<endl;
    for(i=0;i<G.VEXNUM;i++)
    {
        for(j=0;j<G.VEXNUM;j++)
        {
            if(G.ARCS[i][j].length==MAXINT)
            {
                cout<<setw(6)<<"∞";
            }
            else
                cout<<setw(6)<<G.ARCS[i][j].length;
            W++;

            if(W%G.VEXNUM==0)
                cout<<endl;
        }
    }
}


void main()
{

    A=CreatGraph();
    SHORTESTPATH_DIJ(&A);
    printjuzhen(A);

}

图片说明
图片说明
请问怎么可以正确地打印最近的路,而不是按照地点的数字顺序打印出错误的线路。

  • 写回答

1条回答

  • PATIR 2016-12-24 06:49
    关注

    求解答呀,各位大神们,小弟急

    评论

报告相同问题?

悬赏问题

  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择
  • ¥15 这款软件是什么?需要能满足我的需求
  • ¥15 SpringSecurityOauth2登陆前后request不一致