2024年6月2日发(作者：谢晨旭)

标号法

标号法是一种最佳算法，多用于求图的最短路问题。

一、标号法的概念：

所谓标号，是指与图的每一个顶点相对应的一个数字。标号法可以说是动态规划，它

采用顺推的方法，对图的每一边检测一次，没有重复的回溯搜索，因此标号法是一种最佳

算法。

二、标号法的算法流程：

现有一图G，求从起点Vs到终点Ve的最短距离。 设：

Sum(j)───顶点Vj的标号，代表的是Vs到Vj的最短距离。

Vj•已标味着Vs到Vj的最短路以及这条路径的长度已求出。

M(i,j)───Vi到Vj的非负长度。

H(j)───顶点Vj的前趋结点。 标号法的算法流程如下：

sum（s）←0

↓

Vs进入队列L

↓

-----→移出队列L的队首Vk←-----

| ↓ |

| Vk是不是Ve------------------|---→计算结束打印路径

| N∣ Y |

| ↓ |

| 由Vk扩展出结点Vj |

| （Vk与Vj之间相连） |

| Sj←Sum(k)+M(k，j) |

| ↓ |

| Sj小于Sum（j） |

| | |

2024年6月2日发(作者：谢晨旭)

标号法

标号法是一种最佳算法，多用于求图的最短路问题。

一、标号法的概念：

所谓标号，是指与图的每一个顶点相对应的一个数字。标号法可以说是动态规划，它

采用顺推的方法，对图的每一边检测一次，没有重复的回溯搜索，因此标号法是一种最佳

算法。

二、标号法的算法流程：

现有一图G，求从起点Vs到终点Ve的最短距离。 设：

Sum(j)───顶点Vj的标号，代表的是Vs到Vj的最短距离。

Vj•已标味着Vs到Vj的最短路以及这条路径的长度已求出。

M(i,j)───Vi到Vj的非负长度。

H(j)───顶点Vj的前趋结点。 标号法的算法流程如下：

sum（s）←0

↓

Vs进入队列L

↓

-----→移出队列L的队首Vk←-----

| ↓ |

| Vk是不是Ve------------------|---→计算结束打印路径

| N∣ Y |

| ↓ |

| 由Vk扩展出结点Vj |

| （Vk与Vj之间相连） |

| Sj←Sum(k)+M(k，j) |

| ↓ |

| Sj小于Sum（j） |

| | |