XIANG Wenli.A Coherent Approach for Transportation Network Analysis[J].Journal of Chengdu University of Information Technology,2021,36(02):162-168.[doi:10.16836/j.cnki.jcuit.2021.02.007]
传输网络分析
- Title:
- A Coherent Approach for Transportation Network Analysis
- 文章编号:
- 2096-1618(2021)02-0162-07
- 关键词:
- 传输网络; 节点; 连接性; 最小生成树算法; Dijkstra算法
- Keywords:
- transportation network; nodes; connectivity; Minimum Spanning Tree algorithm; Dijkstra’s algorithm
- 分类号:
- TP393.02
- 文献标志码:
- A
- 摘要:
- 分别介绍了基于最小生成树算法和Dijkstra算法的传输网络分析方法。通过引入传输网络的概念,分析了网络连通性。网络连通性是传输网络中的重要一环,其作用在于提供A点到B点间的多种模式连接。通过对网络连通性的分析,可极大地缩短节点间的连接路径,加大流量处理并生成相关信息。通过使用最小生成树算法和Dijkstra算法,将传输网络中的节点信息进行了量化处理。其中,通过最小生成树算法,分析、筛选出了连接首末两点间的最短路径; 通过Dijkstra算法,分析、筛选出了连接首末两点间成本最低的路径。
- Abstract:
- This paper presents a coherent approach to the analysis of transportation network based on the concept of Minimum Spanning Tree algorithm and Dijkstra’s algorithm. Network connectivity is an important aspect of any transportation network, the role of connectivity is to provide a connection to possibly travel from point A to point B by using various modes. The importance of node is, for example, greatly contribute to short connections between nodes, handle a large amount of the traffic, generate relevant information. In order to quantify the relative importance of nodes, we use two algorithm. The first one is Minimum Spanning Tree algorithm, we use it to find the shortest route between two point. The second one is Dijkstra’s algorithm we use it to find the route with lowest cost between two point.
参考文献/References:
[1] Fredman M L,Tarjan R E.Fibonacci heaps and their uses in improved network optimization algorithms[J].Journal of the ACM,1987,34(3):596.
[2] Gabow H N,Galil Z,Spencer T,et al.Efficient algorithms for finding Minimum Spanning Trees in undirected and directed graphs[J].Combinatorica,1986,6(2):109.
[3] Chong Kawong,Han Yijie,et al.Concurrent threads and optimal parallel Minimum Spanning Trees algorithm[J].Journal of the Association for Computing Machinery,2001,48(2).
[4] Bader David A,Cong Guojing.Fast shared-memory algorithms for computing the minimum spanning forest of sparsegraphs[J].Journal of Parallel and Distributed Computing,2006,66(11):1366-1378.
[5] Dahlhaus E,Johnson D S,Papadimitriou C H,et al.The complexity of multiterminal cuts[J].SIAM Journal on Computing,1994,23(4):864-894.
[6] Nicos Christofides.Worst-case analysis of a new heuristic for the travelling salesman problem[C].Graduate School of Industrial Administration,CMU,1976.
[7] Fredman Michael Lawrence,Tarjan Robert E.Fibonacci heaps and their uses in improved network optimization algorithms[J].25th Annual Symposium on Foundations of Computer Science.IEEE.1984.
[8] Fredman Michael Lawrence,Tarjan Robert E.Fibonacci heaps and their uses in improved network optimization algorithms[J].Journal of the Association for Computing Machinery,1987,34(3):596-615.
[9] Zhan F Benjamin,Noon Charles E.Shortest Path Algorithms:An Evaluation Using Real Road Networks[J].Transportation Science,1998,32(1):65-73.
备注/Memo
收稿日期:2020-12-29