注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mister.Hu(巷里人家)

Go abroad!

 
 
 

日志

 
 
关于我

A campus photograph palyer,an enthusiastic reader,a solitary writer,a future traffic engineer.

网易考拉推荐

交通流单位流率戴尔算法C++代码实现  

2015-07-14 21:10:27|  分类: Senior |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
#include <iostream.h>
#include <stdio.h> //调用printf()函数
#include <math.h>//调用exp()函数
#include <string.h>//调用字符串函数
void main()
{
int i,j,k; 
double weight[100][100];//weight[100][100]用于储存边的权值;
    int Dir[10000]; //Dir[10000]用来记录临时标号
memset(&weight,NULL,sizeof(&weight));//对各数组进行清零操作
int PON,EDN;//PON 为点数,EDN为边数
int be,en,we;//be,en,we分别表示每个路段的起点、终点和权值
printf("welcome to use this program!\n");
printf("请输入图形点数:");
scanf("%d",&PON);
printf("请输入图形边数:");
scanf("%d",&EDN);
printf("请输入各边的起点、终点、权值(各值以空格区分,每输完一组请回车):\n");
for(i=1;i<=EDN;i++)
{
printf("请输入第%d条边:",i);
scanf("%d%d%d",&be,&en,&we);
weight[be][en]=weight[en][be]=we;
}
for (i=1;i<=PON;i++)
for(j=1;j<=PON;j++)
{
if(weight[i][j]==0)
weight[i][j]=100000;//将权重为0的路段权重标记为100000
}
int QD,ZD;//QD表示计算起点,ZD表示计算终点
printf("现在输入起点:");
scanf("%d",&QD);
getchar();
printf("现在输入终点:");
scanf("%d",&ZD);
getchar();
printf("\n#### ####以下是当起点为%d,终点为%d的详细情况########\n",QD,ZD);
int per[100],perb[100],used[100],f[100];  //per[100]为永久标号;used[100]用于标记遍历过的节点;f[100]为一次计算内的永久标号,perb[100]为per[100]的存档
per[QD]=0;            //计算各点标号
for(j=1;j<=PON;j++)
{
int h;
if(j==QD)
continue;
ZD=j;//将j赋值为本次计算的终点
h=QD;//将本次计算的起点标号赋值为h
f[QD]=0;//将本次计算的起点永久标号记为0
for(i=1;i<=PON;i++)
{
Dir[i]=100000;//将每一个点的临时标号设为100000
used[i]=0;//说明没有一个点被遍历过,u[i]=0说明没有被遍历,u[i]=1说明被遍历。
}
used[QD]=1;        //从起点开始遍历(广度遍历),首先表示起点被遍历了
while(used[ZD]!=1)//保证终点未被遍历
{
for (i=1;i<=PON;i++)
{
if(used[i]==1)//保证i没有被遍历(u[i]=1说明该点被遍历过了)
continue;
if(weight[h][i]!=100000)//保证w[h][i]不等于0
{
if((f[h]+weight[h][i])<Dir[i])//若起点h的本次永久标号加上h-i路段的权重小于i的临时标号,则将f[h]+w[h][i]赋值给i作为其标号
{
Dir[i]=f[h]+weight[h][i];
}
}
}
we=Dir[1];//寻找Dir[i]中的最小值并最终赋值给c,k用于标记该最小值对应的点的编号
k=1;
for (i=2;i<=PON;i++)
{
if (we>Dir[i])
{
we=Dir[i];
k=i;
}
}
h=k;//将上一步对应的编号最小值赋值给新一轮的起点h,继续进行重复的步骤
per[h]=f[h]=Dir[h];//将h点(也就是之前找出的k)的Dir[h]赋值给v[h]和f[h]用作永久编号和新一轮计算的永久编号
Dir[h]=100000;
used[h]=1;//(将h点记录为被遍历过的点)
}
}
printf("各点的标号为:\n");//输出各点的编号
for (i=1;i<=PON;i++)
{
printf("%d\t",per[i]);
perb[i]=per[i];//将per[i]备份一份到perb[i]
}
printf("\n");
int bordn[100],bord[100][100];//bordn[100]表示邻接点数,bord[i][k]=j表示与i相邻的第k个点为j
for(i=1;i<=PON;i++)   //求邻接矩阵,即与各点相连的点
{
bordn[i]=0;
k=0;
for(j=1;j<=PON;j++)
{
if (weight[i][j]!=100000)//权重为100000的表示该两点不相连或相连但权重为0,也视为不相连
{
bordn[i]++;
k++;
bord[i][k]=j;//k用于标记与i相邻的点为第几个,即bord[i][k]=j表示与i相邻的第k个点为j
}
}
}
int rea[100][100],rest[100][100];//rea[i][t]表示在合理路径中与i相邻的第t个点的号码,rest[i][t]表示在非合理路径(即其余路径)中与i相邻的第t个点的号码
rea[0][0]=0;
for(i=1;i<=PON;i++)   //求合理路径,即与各点相连比自己标号大的点,rea[i][0]表示点数
{
int s,t;
rea[i][0]=rest[i][0]=0;
s=t=0;
for(j=1;j<=bordn[i];j++)
{
if (per[i]<per[bord[i][j]])//如果i的永久标号小于与之相邻的,则rea[i][0]加1,并将与i相邻的第j个点的号码赋值给rea[i][t]
{
rea[i][0]++;
s++;
rea[i][s]=bord[i][j];//rea[i][t]表示在合理路径中与i相邻的第t个点的号码。
}
if (per[i]>per[bord[i][j]])//如果i的永久标号大于与之相邻的,则rest[i][0]加1,并将与i相邻的第j个点的号码赋值给rest[i][t]
{
rest[i][0]++;
t++;
rest[i][t]=bord[i][j];
}
}
}
int reaj,o,r;//reaj用于记录合理路径上的点的号码;o用于输出编号;
double p[100][100];//p[100][100]用于记录合理路段的使用概率;
double pw[100],lw[100][100],Q[100][100],PQ[100];//pw[100]为点权,lw[100][100]表示线权,PQ[100]表示点的单位流率(即从该点流入流出的流量);Q[100][100]表示路段的单位流率
int rank[100],l[100];    //rank[100]用来记录标号的排序;l[100]用以记录遍历过的点
for (i=1;i<=PON;i++)   //求各合理路段被使用的概率
{
for (j=1;j<=rea[i][0];j++)
{
reaj=rea[i][j];//将合理路径上与i相邻的第j个点的号码赋值给reaj
r=per[reaj]-per[i]-weight[i][reaj];//s等于reaj点的永久标号剪去reaj前一点i的永久标号加上路段i-reaj的权重
p[i][reaj]=p[reaj][i]=exp(r);//将e的s次方记录在p[i][reaj]中,即为路段使用概率
}
}
for (i=1;i<=PON;i++)//初始化各参数为0
{
l[i]=0;//初始没有点被遍历
pw[i]=0.0;//各点点权赋值为0
PQ[i]=0.0;//
for(j=1;j<=PON;j++)
{
lw[i][j]=0.0;//各线线权赋值为0
Q[i][j]=0.0;
}
}
pw[QD]=1.0;//将起点的点权赋值为1
for (i=1;i<=PON;i++)
rank[i]=i;//将点i的标号赋值给rank[i],rank[i]表示按永久编号升序顺序排好的点的号码
for(i=1;i<PON;i++)    //将各点标号排序,以便于按照一定的顺序遍历
for(j=i+1;j<=PON;j++)
{
if(perb[i]>perb[j])//对每个点的永久标号进行从小到大的排序
{   
int p;
p=rank[i];
rank[i]=rank[j];
rank[j]=p;
p=perb[i];
perb[i]=perb[j];
perb[j]=p;
}
}
o=1;
for (i=1;i<=PON;i++)   //显示各路段的线权
{
for (j=1;j<=rea[rank[i]][0];j++)
reaj=rea[rank[i]][j];
lw[rank[i]][reaj]=pw[rank[i]]*p[rank[i]][reaj];//该点的线权为该点点权乘以该路段对应的路段使用概率
printf("(%d)点%d和点%d路段线权为%3.2f\t",o,rank[i],reaj,lw[rank[i]][reaj]);
pw[reaj]=pw[reaj]+lw[rank[i]][reaj];//计算该点的点权:该点的点权等于以该点为终点的各线线权之和;
printf("\n");
o++;
}
}
printf("\n");
for (i=1;i<=PON;i++)   //显示各点点权
{
printf("(%d)点%d的点权为%3.2f:\t",i,i,pw[i]);
printf("\n");
o++;
}
printf("\n");
int x,y,z;
PQ[ZD]=1.0;//将计算终点的单位流率赋值为1
for(k=1;k<=PON;k++)
if(rank[k]==ZD)
x=k;//将按永久编号升序顺序排好的点的号码对应的计算终点的那个号码赋值给y
l[rank[x]]=1;//将终点标记为已遍历
for(i=x;i>0;i--)//从终点开始往回遍历各点
{
if(rea[rank[i]][0]==0&&l[rank[i]]==0)   //表示在合理路径中以点rank[i]为起点的点数为0且该点未被遍历过。则跳出循环
continue;
for(j=0;j<=rest[rank[i]][0];j++)   //计算当前点和其合理路段上游点的单位流率
{
Q[rest[rank[i]][j]][rank[i]]=lw[rest[rank[i]][j]][rank[i]]*PQ[rank[i]]/pw[rank[i]];//计算路段"rest[rank[i]][j]-rank[i]"(即非合理路径上与rank[i]相邻的第J个点与rank[i]之间的路段)的单位流率.应注意此处是从终点往回走,所以相对于起点-终点的合理路径在此处恰好是非合理路径
}
for (k=x;k>0;k--)   //选择下面一个要进行单位流率计算的点
{
if(l[rank[k]]==1)//若点rank[k]被遍历过,则此次循环终止
continue;
if(l[rank[k]]==0)
{
y=rea[rank[k]][0];
for (z=1;z<=rea[rank[k]][0];z++)
{
if(l[rea[rank[k]][z]]==0)
y--;
}
}
if(y==0)
continue;//若与点rank[k]相连的合理路径上的另一端点都被被遍历过,则此次循环终止
if(y>0)
break;//若与点rank[k]相连的合理路径上的另一端点有未被遍历的,则跳出整个循环体,即,执行reaj=k,将判断出的k值赋给reaj作为要计算的下一个点
}
reaj=k;//将判断出的k值赋给reaj作为要计算的下一个点
int a;
for (a=1;a<=rea[rank[reaj]][0];a++)   //计算点的单位流率
{
PQ[rank[reaj]]=PQ[rank[reaj]]+Q[rank[reaj]][rea[rank[reaj]][a]];//点的单位流率等于原来该点的单位流率加上以该点为起点的各路段对应的路段单位流率
l[rank[reaj]]=1;//将该点标记为已遍历
}
}
o=1;
for(i=1;i<=PON;i++)//输出单位流率
for(j=rea[i][0];j>0;j--)
{
printf("(%d)点%d到点%d的单位流率为:%3.2f\t",o,i,rea[i][j],Q[i][rea[i][j]]);
printf("\n");
o++;
}
printf("\n");
printf("########以上是当起点为%d,讫点为%d的详细情况########\n\n",QD,ZD);
printf("本计算单位流率代码程序由完成,学号:\n\n");
}

  评论这张
 
阅读(25)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016