|
1. 带权图中，边带有一个数字，叫做权，它可能代表距离、耗费、时间或其他意义。 2. 带权图用来最常解决的问题是最短路径问题（pps）。 3. 带权图的最小生成树中有所有的顶点和连接它们的必要的边，且这些边的权值最小。 4. 优先级队列的算法可用于寻找带权图的最小生成树。 5. 解决无向带权图的最小生成树的方法 1) 找到从最新的顶点到其他顶点的所有边，这些顶点不能在树的集合中，把这些边放如优先级队列。 2) 找出权值最小的边，把它和它所到达的顶点放入树的集合中。 3) 重复以上步骤，直到所有顶点都在树的集合中。 6. 带权图的最短路径问题可以用Dijkstra算法解决。这个算法基于图的邻接矩阵表示法，它不仅能找到任意两点间的最短路径，还可以找到某个指定点到其他所有顶点的最短路径。 Dijkstra算法的思想： 以解决寻找一条从一个城市到另一个城市的费用最低的路线为例（假设不能直接指导所有路线的费用，只能直接知道到邻接城市的费用） 1) 每次派一个代理人到新的城市，用这个代理人提供的新信息修正和完善费用清单，在表中之保留从源点到某个城市现在一直的最低费用 2) 不断向某个新城市派代理人，条件是从源点到那个城市的路线费用最低。 如 7. 有时为了看出某条路线是否可能，需要创建一个连通表。在带权图中，用一张表给出任意两个顶点间的最低耗费，这对顶点可能通过几条边相连。这种问题叫做每一对顶点之间的最短路径问题。Warshall算法（此算法在图章节中详述）能很快创建这样的连通表。在带权图中类似的方法叫做Floyd算法。 Floyd算法与Warshall算法的区别。在Warshall算法中当找到一个两段路径时，只是简单的在表中插入1，在Floyd算法中，需要把两端的权值相加，并插入它们的和。 8. 关于各种图的算法的效率： 图的表示法有两种：邻接矩阵和邻接表 算法 时间级 邻接矩阵（所有）
O（V2） 无权邻接表
O(V + E) 带权邻接表
O((E+V)logV) Warshall和Floyd算法 O（V3） 其中V是顶点数量 |
|
|
