数学建模社区-数学中国

标题: 公交路线最小转乘次数的路径选择算法（C程序代码）（请求仁兄指导） [打印本页]

---

作者: 舞情＿Dong    时间: 2012-8-19 17:58
标题: 公交路线最小转乘次数的路径选择算法（C程序代码）（请求仁兄指导）

第三天了，关于交通路线的选择，用C语言写成了个样子，下面代码可以正常运行，就是路线选择的结果不是很好，结果有好多重复的，有些站点似乎选不出来，这和存放交通路线的数组a有关，我们是把公交路线的上行和下行放在二维数组的同一行的，肯定有重复，但对程序算法也有质疑，实在是惭愧，自己不才，对其它语法实在是不太了解，用的都是for，if循环嵌套，还请仁兄指教。这是2007年的全国竞赛题，网上也有各种算法（基于不同语言），我们建模培训做真题，按自己想法用C编写了下面的程序，但结果不是很好，自己对其它的语句又不是很了解，实在没辙了，真心请教各位大侠，现在在改数组，打算将同一条交通路线的上行和下行放入数组的不同行里，真心寻求帮助，请求仁兄指导，谢谢！

]编写的C代码如下，由于数组a的数据带大，粘贴不过来（520条数据）
本人实在是很惭愧，对C其他语法语句不是很熟悉，用的全是for，if循环嵌套，还请仁兄耐心查看：


uint value1,value2;
        uint a[200],a1[200];//定义一个数组
        uint b[200],b1[200];
     uint c[200];



void routes()
{
       
        uint i,j,j1,j2,j3,j4,c1,c2,k=0,k1=0,k2=0;
        uint linshi1,linshi2,e=0,f=0;
        uint q1,q2,q3,t;
        uint luxian1=0;
        uint m=0;
        uint n=0;
        for(i=0;i<520;i++)
        {
                for(j=0;j<200;j++)
                {
                        if(y[j]==value1)//寻找包含起点的所有路线,将路线值放入数组a
                        {
                                a[m]=i;
                                //a1[m]=j;
                                m++;
                        }
                        if(y[j]==value2)//寻找包含终点的所有路线，将其放入数组b
                        {
                                b[n]=i;
                                //b1[n]=j;
                                n++;
                        }
                }               
        }
        printf("所有经过起点的路线a为：");
        for(i=0;i<m;i++)
        {
                printf("%d  ",a);               
        }
        printf("\n");
        printf("所有经过终点的路线b为：");
        for(i=0;i<n;i++)
        {
                printf("%d  ",b);               
        }
        printf("\n");



        for(i=0;i<m;i++)//直达路线的寻找
        {
                for(j=0;j<n;j++)
                {
                        if(a==b[j])
                        {
                                c[k]=a;
                                k++;                                       
                        }
                }
        }
        printf("您查询的站点的直达路线有：");
        for(i=0;i<k;i++)
        {
                if(c!=0)
                printf("%d  ",c);
        }
        printf("\n");//若没有直达路线这数组c为零，接着下面转乘一次路线的寻找


        if(k==0)
        {
                for(c1=0;c1<m;c1++)//转乘一次路线的寻找
                {
                        for(j=0;j<200;j++)
                        {
                                linshi1=a[c1];
                                k1=y[linshi1][j];//取出a中每一条路线上每一个站点，接着与b中站点进行比较，查询公共点。
                                for(c2=0;c2<n;c2++)
                                {
                                        for(j=0;j<200;j++)//该算法不是很好，j小于200时还得往后遍历。
                                        {
                                                linshi2=b[c2];
                                                k2=y[linshi2][j];//将b中的站点取出与k1进行比较判断。
                                                if(k1==k2/*||k1==k2+1||k1==k2-1*/&&(k1!=0)&&(linshi1!=0)&&(linshi2!=0))//寻找数组a,b中的站点，有相同的及为转乘一次的转乘点，并输出。
                                                {
                                                        printf("您可以转乘一次，起始路线为:%d ，中间转站点为：%d ,%d终点路线为：%d\n",linshi1,k1,k2,linshi2);
                                                        luxian1++;
                                                }
                                        }                               
                                 }       
                        }        
                }
        }


        if(luxian1==0&&k==0)
        {
                for(c1=0;c1<m;c1++)//转乘两次路线的寻找
                {
                        for(j=0;j<200;j++)
                        {
                                linshi1=a[c1];
                                k1=y[linshi1][j];//取出a中每一条路线上每一个站点，接着与b中站点进行比较，查询公共点。
                                for(c2=0;c2<n;c2++)
                                {
                                        for(j=0;j<200;j++)//该算法不是很好，j小于200时还得往后遍历。
                                        {
                                                linshi2=b[c2];
                                                k2=y[linshi2][j];//将b中的站点取出与k1进行比较判断。
                                                for(i=0;i<520;i++)
                                                        {
                                                                for(j=0;j<200;j++)
                                                                {
                                                                if(k1==y[j]&&k1!=0)
                                                                {
                                                                        f=i;
                                                                        e=j;                                                               
                                                                        for(j=0;j<200;j++)
                                                                        {
                                                                                if(k2==y[j]&&k2!=0&&(e<j)&&(linshi1!=0)&&(linshi2!=0))
                                                                                {
                                                                                        printf("您需转乘两次，起始路线为：%d ,第一个转车站点为：%d,中间路线为：%d,第二个转车站点为：%d,终点路线为：%d\n",linshi1,y[e],f,y[j],linshi2);
                                                                                        //q1=abs(e-a1[c1]);//计算每条路线上经过的站点数
                                                                                        //q2=abs(j-e);
                                                                                        //q3=abs(b1[c2]-j);
                                                                                        //t=3*(q1+q2+q3)+10;
                                                                                        //printf("该路线总共计时为：%d 分钟\n",t);
                                                                                }
                                                                        }
                                                                }
                                                                }
                                                        }   
                                        }       
                                }
                        }

                }
        }












}

        void main()
        {
                printf("请输入起始站点和终止站点（中间空格间开）: \n");
                scanf("%d %d",&value1,&value2);
                /*zhida();               
                zhuancheng1();
                zhuancheng2();*/
                routes();

        }

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5