最短路的几个算法的代数证明

摘要

＜正＞ 一、引言设有一个有向图,顶点集合为V={Vi|i=1,2,…n),有向边集合记作E。对于每一条边,赋以一个实数,可正、可负、可为零,这个实数叫做这条有向边的长度。这样的有向图叫做（一般）网络,记作N（V,E）。我们把在网络中寻求各顶点间的最短路的长度问题叫做求解模型MINPATH。而找出最短路叫做模型MINPATH的解的实现。网络中如果含有负回路,则有些顶点间,尽管存在长度有限的路,却不一定存在最短