1 最短通路问题
最短通路问题 1
上节回顾 口内容1：欧拉图 口什么是欧拉图：含有欧拉回路 口欧拉图的充要条件：所有顶点度数为偶数 口如何构造欧拉回路：Fleuty算法 口内容2：哈密尔顿图 口什么是汉密尔顿图：含有汉密尔顿回路 ▣哈密尔顿图的必要和充分条件： ■必要条件：P(G-S)≤S,只能用来判断一个图不是汉密尔顿图 ■充分条件：Ore定理，只能用来判断一个图是汉密尔顿图 口哈密尔顿图有哪些应用
内容1：欧拉图 什么是欧拉图：含有欧拉回路 欧拉图的充要条件：所有顶点度数为偶数 如何构造欧拉回路：Fleury算法 内容2：哈密尔顿图 什么是汉密尔顿图：含有汉密尔顿回路 哈密尔顿图的必要和充分条件： ◼ 必要条件：P(G-S) |S|，只能用来判断一个图不是汉密尔顿图 ◼ 充分条件：Ore定理，只能用来判断一个图是汉密尔顿图 哈密尔顿图有哪些应用 上节回顾
本节提要 ▣内容1：Dijkstra算法 口内容2：Floyd-Warshall:算法 ▣内容3：旅行商问题(TSP) ▣内容4：最大流问题
内容1：Dijkstra算法 内容2：Floyd-Warshall算法 内容3：旅行商问题（TSP） 内容4：最大流问题* 本节提要
Dijkstra算法 4 Named after its inventor Edsger Dijkstra (1930-2002) Truly one of the "founders"of computer science This is just one of his many contributions
Dijkstra算法 4 Named after its inventor Edsger Dijkstra (1930-2002) Truly one of the "founders" of computer science This is just one of his many contributions
带权图与最短通路问题 口带权图：三元组(V,E,，(V,E是图，W是从E到 非负实数集的一个函数。W(e)表示边e的权。 口一条通路上所有边的权的和称为该通路的长度。 两点之间长度最小的通路称为两点之间的最短通路， 不一定是唯一的。 口单源点最短路问题 给定带权图G(V,E,)并指定一个源点，确定该源 点到图中其它任一顶点的最短路径
带权图：三元组 (V, E, W)，(V, E)是图，W是从E到 非负实数集的一个函数。W(e)表示边e的权。 一条通路上所有边的权的和称为该通路的长度。 两点之间长度最小的通路称为两点之间的最短通路， 不一定是唯一的。 单源点最短路问题 给定带权图 G(V, E, W)并指定一个源点，确定该源 点到图中其它任一顶点的最短路径。 带权图与最短通路问题