International Open Access Journal Platform

有向图中的最短路径、关键路径的解决方法探析

The solution of shortest path and critical path in directed graph

Applied Mathematics Information / 2019,1(1): 16-28 / 2019-12-27 760 580

View Download PDF

• Authors: 刘芊     
• Information:

  江西师范大学，南昌

• Keywords: Grdbner 基；约化；路径；权值
• Grdbner base; Reduced; The path; A weight
• Abstract: 对于一个给定的有向图G，G 中两个相邻顶点vi → vj 的路径可以用多 项式vi → vj 来表示，并用dij 记其边的权值，而dij 可由在Ω={0，1} 的范围内 解线性方程组来确定。该结果可以用来解决有向图的最短路径、关键路径等问题， 并且此方法还可推广到无向图，用来解决哈密顿道路和回路，欧拉道路和回路 等问题。
• Given a directed graph G, G of two adjacent vertex vi to vj paths can use polynomial vi, vj, and dij remember the edge has a weight, and dij may consist in Ω = {0, 1} within the scope of the solution system of linear equations to determine. The results can be used to solve the shortest path and critical path problems of directed graphs, and the method can also be extended to undirected graphs to solve Hamiltonian roads and circuits, euler roads and circuits and other problems.
• DOI: https://doi.org/10.35534/ami.0101004c
• Cite: 刘芊．有向图中的最短路径、关键路径的解决方法探析［J］．应用数学资讯，2019，1（1）：16-28．