Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path

FENG Lin-yao; YUAN Lin-wang; LUO Wen; LI Run-chao; YU Zhao-yuan

doi:10.3969/j.issn.0372-2112.2014.05.003

您当前的位置：

首页 >

文章列表页 >

Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path

更新时间：2025-07-16

- Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path
- Acta Electronica Sinica Vol. 42, Issue 5, Pages: 846-851(2014)
- 作者机构：
  
  1. 南京师范大学虚拟地理环境教育部重点实验室,江苏,南京,210023
  2. 南京师范大学江苏省大规模复杂系统数值模拟重点实验室,江苏,南京,210023
  3. 南京师范大学虚拟地理环境教育部重点实验室,江苏,南京,210023
  4. 南京师范大学江苏省大规模复杂系统数值模拟重点实验室江苏南京,210023
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2014.05.003
  CLC： P208TP301.6
- Published：2014
- 稿件说明：
移动端阅览
FENG Lin-yao, YUAN Lin-wang, LUO Wen, et al. Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path[J]. Acta Electronica Sinica, 2014, 42(5): 846-851.
DOI：

FENG Lin-yao, YUAN Lin-wang, LUO Wen, et al. Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path[J]. Acta Electronica Sinica, 2014, 42(5): 846-851. DOI： 10.3969/j.issn.0372-2112.2014.05.003.

摘要

面向网络分析应用中复杂条件约束下的最短路径求解问题，引入几何代数进行网络分析算法构造.建立了基于几何代数的网络模型和双边搜索算法，以寻找经过指定必经节点且弧段最少的最短路径求解为例，进行了算法实现.基于道路网络数据的分析显示，本算法利用外积运算直接判断约束节点，算法具有更好的通用性和较少的路径遍历次数，且在多对多路径求解及多用户并行求解上具有优势.

Abstract

Focusing on the solving of the shortest paths in the conditions of complicated constraints for network analysis and application

geometric algebra is used to develop the network analysis algorithms.We built a network model and bilateral search algorithms based on the multivector representation and multidimensional operators of geometric algebra.Then

we implemented the algorithm by taking the example of finding the shortest paths that pass the specified necessary nodes and the least segments.According to the experiment analysis of the road network data

this algorithm can directly estimate the constrained nodes by applying the outer algorithm and has better versatility and less path traversal times.Moreover

this algorithm has an advantage on many-to-many path solution and multi-user parallel solution.

关键词

Keywords

references

Views

2979

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Joint DOA and Polarization Estimation of Unequal Power Sources for Electromagnetic Vector-Sensor Array Based on Geometric Algebra

Finding the Shortest Path Based on Delay PCNN

Geometric Algebraic Method for Behavior Trajectory Reconstruction in PIR Sensor Networks

Related Author

WANG Tong

LIU Shang-he

CHEN Dong-wei

JIN Meng-zhe

FANG Qing-yuan

GU Xiao-dong

YU Dao-heng

ZHANG Li-ming

Related Institution

Hebei Key Laboratory for Electromagnetic Environmental Effects and Information Processing, Shijiazhuang Tiedao University

National Key Laboratory on Electromagnetic Environment Effects, Army Engineering University of PLA

Department of Electronic Engineering, Fudan University

Department of Electronics, National Laboratory on Machine Perception and Center of Information Science,Peking University

Department of Electronic EngineeringFudan UniversityShanghai 200433China

⁰