BFS广度优先搜索过程 5搜索完成 A B D C)3 6 HGFEDCBA 队列变化情况 箭头表示当前访问节点
BFS 广度优先搜索过程 AD C EG B F H I 1 2 4 3 5 6 7 8 9 FEDCABGHI 队列变化情况 箭头表示当前访问节点 指针 搜索完成
广度优先搜索S到T的搜索路径 上午231 土年23 凹「 图89广度优先搜索过程1图3-10广度优先搜索过程2
◼ 广度优先搜索S到T的搜索路径 S T S T
(3)路径搜索算法 Dijkstra 口 Dijkstra算法是典型的最短路径算法,一般用于求出 从一点出发到达另一点的最优路径,但是,因为其 遍历运算的节点较多,所以运行效率较低。 23节点 径树 2,3→节点5 23→节点5 降径树 节点2 0.326 节点2 032 节点2 03 小点,0326 0强c到0 222 218c0m 3g4n.com 212 L技术成节3 就梦想 点3成就梦想 和1就梦想 短径树 2,3→节点5 节点5 032 节 点2 03 节点4 22 某成就参想
（3）路径搜索算法—Dijkstra ❑ Dijkstra算法是典型的最短路径算法，一般用于求出 从一点出发到达另一点的最优路径，但是，因为其 遍历运算的节点较多，所以运行效率较低
最短通路问题 Shortest-Path problems 定义:设图G=<V,E>,给定W:E→R,对G的每条边e, 称W(e)为边e的权。把这样的图称为带权图,记作G=V,E,W> 设P是G中的一条通路,P中所有边的权之和称为P的长度, 记作:W(P)=∑ e∈E(P)
最短通路问题 Shortest-Path Problems ◼ 定义：设图G =<V,E>，给定 , 对G的每条边e， 称W(e)为边e的权。把这样的图称为带权图，记作 ◼ 设P是G中的一条通路，P中所有边的权之和称为P的长度， 记作： W : E → R G =V,E,W = ( ) ( ) ( ) e E P W P W e
最短通路问题 Shortest-Path problems 1例 W(ab)=5, W()=0 12 4 W(bd)=∞, W(ad)=8 20
最短通路问题 Shortest-Path Problems w(ab)=5， w(aa)=0， w(bd)= ∞ ， w(ad)=8 a b d c 5 8 12 4 20 ◼例：