利用Dijkstra算法与Floyd算法进行交通分配比较分配结果摘要：本文主要内容包括对乌鲁木齐市五区的人民进行OD调查，得到网络交通量数据，再利用Dijkstra算法与Floyd算法确定交通网络图的最短路径，运用全有全无的方法进行交通量的分配，最后比较这两种方法在确定最短路径时的利弊。

关键词：Using the algorithm of Dijkstra and Floyd to distribute the volume of traffic and compare the result of the traffic assignment Abstract: The article takes the main point to use the algorithm of Dijkstra and Floyd to decide the shortest way of traffic network , making use of the method of All-or-none to distribute the volume of traffic. At last,comparing the advantages and disadvantages between the two methods during deciding the shortest way.Key word:0．引言：随着科学技术的进步和工业的发展，城市中交通量激增，城市道路交通拥堵和环境污染现象越来越严重，对人民的出行和生活带来了很大的不便和危害，私人交通工具发展的结果，给城市交通带来了一系列的问题，主要是：①交通拥挤和交通阻塞，城市中的平均车速日益下降;②交通事故增加；③噪声和空气污染日趋严重;④能源消耗量猛增；⑤停放车场地严重不足。

为了克服这些矛盾，一些工业发达的国家，曾致力于道路系统的改善：加宽地面道路，修建高架路和高速路，开辟地下交通。

此外，在交通管理、交通控制系统方面采用了计算机等新技术。

这些措施虽然提高了道路通过能力，但是仍解决不了由有增无减的私人交通流所造成的道路阻塞问题。

就道路交通拥堵问题，这里运用Dijkstra算法与Floyd算法确定交通网络的最短路径，并用全有全无的方法进行交通量得分配，最后比较这两种方法在确定最短路径时的难易程度。

1．规划区社会经济发展概况1.1 乌鲁木齐是新疆维吾尔自治区首府，全疆政治、经济、文化中心，也是第二座亚欧大陆桥中国西部桥头堡和我国向西开放的重要门户。

她地处亚欧大陆中心，天山山脉中段北麓，准噶尔盆地南缘。

乌鲁木齐经济建设长足进步。

改革开放以来，特别是国家实施西部大开发战略以来，乌鲁木齐经济建设取得了前所未有的成就。

以国有企业为中心的各项改革取得显著成效，建立和完善了社会主义市场经济体制，全方位的开放开发格局初步形成。

经济结构战略性调整取得实质性进展，经济技术开发区、高新技术产业开发区和区级经济成为新的经济增长点，公有制为主体、混合所有制经济共同发展的格局基本形成。

农村经济稳步发展，农业结构调整力度加大。

工业结构调整继续深化，高新技术产业产值的比重不断提高。

城市基础设施功能不断完善，建成了以中山路商业一条街、人民路金融一条街、二道桥民俗一条街和北京路科技一条街为主要代表的、各具特色的城市功能街区。

新疆商贸城、中国新疆小商品城、新疆国际大巴扎、华凌、友好百盛等一批地方特色市场和大型超市相继建成，逐步形成了火车南站、二道桥、中山路、大西门、铁路局等各具特色、初具规模的商业圈，肯德基、普尔斯玛特、世纪金花、百盛、家乐福等一批国内外著名品牌流通企业落户我市。

2007年，全市生产总值820.28亿元，人均生产总值3.11万元，地方全口径财政收入95.8亿元，社会消费品零售总额332.4亿元，城镇居民人均可支配收入11373元。

在西部12个首府、省会城市中，综合竞争力位居前列。

1.2.21.2.31.2.41.2.51.2.61.3.1沙依巴克区2010年国民生产总值预测1.3.2天山区2010年国民生产总值预测1.3.51.4 由以上两个折线图可以看书，乌鲁木齐五区的人口与国民生产总值在不断提高，人民生活质量日益增加。

乌鲁木齐居民在食品消费上逐步向营养、科学、多样化方向发展，居民的饮食更多地追求食品的口感、方便和营养，以此也拉动了食品消费的支出，三季度人均月食品支出达到了207.12元，同比增长了9.17％。

衣着消费方面，居民所追求的档次高了，三季度居民家庭人均月衣着支出59.07元，同比增长11.15％。

同时，通信业的飞速发展，激发了人们对高科技信息产品和服务的需求渴望，引发消费热潮，居民用于通讯方面的支出大幅增长。

三季度，居民人均月通讯支出达到了39.26元，同比增长15.64％。

2 主要方法介绍2.1 OD调查方法2.1.1 OD调查即交通起止点调查又称OD交通量调查，OD交通量就是指起终点间的交通出行量。

“O”来源于英文ORIGIN，指出行的出发地点，“D”来源于英文DESTINATION，指出行的目的地。

2.1.2 OD调查方法很多。

在我国，客流OD调查多采用家访调查，货流调查多采用发收表调查。

家访调查是对居住在调查区内的住户，进行抽样家访。

由调查员当面了解该户中包括学龄前儿童在内的6年以上（如北京1986年进行的个人出行调查）全体成员的详细出行情况，包括出发地、出发时间、目的地、到达目的地的时间、交通工具、出行目的、换乘情况、上车前后的步行时间等。

这种调查方法数据可靠，而且还可同时得到出行者的个人属性及社会经济特征资料。

发收表调查是将调查表格发到卡车驾驶员处，由驾驶员逐项填写。

主要包括发时、抵时、货种、载重、起止点路段名和单位名，经过主要路口、里程等。

事实证明，这两种调查方法的调查效果都很好。

此外还有路边询问调查、明信片调查、工作出行调查、车辆牌照调查、运输集散点调查、公交线路乘客调查、电话询问调查等。

每种方法都各有优缺点，可根据实际情况加以选用，也可以同时采用几种方法，以互补不足或互相校对。

2.2 Dijkstra算法2.2.1Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。

注意该算法要求图中不存在负权边。

2.2.2 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。

在加入的过程中，总保持从源点v到S 中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。

此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2.2.3 算法具体步骤（1）初始时，S只包含源点，即S＝，v的距离为0。

U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。

（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中。

2.3 Floyd算法2.3.1 Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。

2.3.2核心思路：通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。

矩阵D(n)的i行j列元素便是i号顶点到j 号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵方向来记录两点间的最短路径。

2.3.3 算法过程：把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。

定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。

把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。

在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。

3 分析模型建立3.1 OD调查方案居民出行调查生活区一、方法：家庭访问法二、定义：对调查区内的家庭，按确定的抽样率进行家庭访问，多用于居民出行调查，调查员当面了解被调查户中包括就学儿童在内的家庭成员全天出行情况，家庭访问法是搜集居民出行资料最可靠的方法之一。

三、确定抽样率：根据城市规模、人口和区域划分，对居民进行抽样调查，、乌鲁木齐市人口数约两百万人，大于100万人时按1/25抽样，即共应抽样8万人进行调查。

四、问卷设计3.2绘图及数据汇总处理A代表沙依巴克区；B代表天山区；C代表水磨沟区；D代表新市区；E代表米东新区调查表格发放8万份，收回7万9千6百余份，符合调查要求。

经调查得到各个路段的通行时间和通行能力：经问卷调查及数据汇总预测各个区之间的交通量：3.3 分别用Dijkstra算法与Floyd算法确定最短路径（见下一页）3.4 用全有全无方法进行交通量的分配。