Gr bner基理论在最短路径问题中的应用

来源期刊：中南大学学报(自然科学版)2002年第6期

论文作者：陈小松 彭丰富

文章页码：648 - 650

关键词：最短路径;Grōbner基;约化

Key words：optimal route; Grōbner basis; reducing

摘    要：在最短路径问题中,若连通图中相邻节点对x_i和x_j间的路径长为a_ij,则节点之间的关系可用多项式x_i-x_j-a_ij描述,把所有的这种多项式以终点所表示的项为首项归纳和排序得到集合F,若存在最短路径供选择,则F生成理想的Gr bner基为{1}.因此,求节点x_m到x_k的最短路径,可用多项式x_k-x_m对F中的元素约化,所得到的一个常数就是这条可达路径的长度;若有多条路径可供选择,则每条路径对应一个常数,所有这些常数中的最小数就是最短路径的长度.

Abstract: There are a pair of adjacent jointsxiandxj. Let the length of route from x_i to x_j be a_ij, and they can be expressed by a polynormal asx_i-x_j-a_ij. Categorizing all this kind of polynomals in the graphic according to their leading terms, and sequencing this categories, they form a polynomial tableF. If there is a shortest route between x_m and x_k,which are random knots in the graphic, the Gr bner basis of generated idea by the set of polynomials is {1}. Assumeing whatwe research is the shortestroute from x_m to x_k, using x_k-x_m reducing the unit of table F according to a sequence,a constant through reduction can be got, and then point x_m can reach point x_k. Because there are many different routes between x_m and x_k, there are a group of constants through different sequences of reduction. The minimal constant is the shortest route.