什么是加权模型？

1.在加权图中，边有一个数字叫做权重，它可能代表距离、成本、时间或其他含义。

2.用加权图解决的最常见的问题是最短路径问题(pps)。

3.赋权图的最小生成树中有所有顶点和连接它们的必要边，这些边的权值最小。

4.优先级队列算法可以用来求赋权图的最小生成树。

5.无向赋权图最小生成树的求解方法。

1)找到从最新顶点到其他顶点的所有边，这些边不能在树的集合中，把这些边作为优先级队列。

2)找到权重最小的边，把它和它到达的顶点放入树的集合中。

3)重复上述步骤，直到所有顶点都在树的集合中。

6.加权图的最短路径问题可以用Dijkstra算法求解。该算法基于图的邻接矩阵表示。它不仅可以找到任意两点之间的最短路径，还可以找到从一个指定点到所有其他顶点的最短路径。

Dijkstra算法的思想；

以寻找一条从一个城市到另一个城市成本最低的路线为例(假设所有路线的成本都无法直接导得，只能直接知道到邻近城市的成本)。

1)一次派一个代理到一个新的城市，利用这个代理提供的新信息修改完善费用清单，把从源头点到表中某个城市的最低费用保留下来。

2)不断向一个新的城市派遣代理，前提是从源头点到那个城市的路线成本最低。

画

7.有时候为了看一个路由是否可行，需要创建一个连接表。在加权图中，表格用于给出任意两个顶点之间的最小成本，这两个顶点可能由几条边连接。这个问题叫做每对顶点之间的最短路径问题。Warshall算法(该算法在图章中有详细介绍)可以快速创建这样的连接表。加权图中类似的方法叫做弗洛伊德算法。

Floyd算法和Warshall算法的区别。当Warshall算法中找到一条两段路径时，简单来说就是将1插入表中。在Floyd算法中，需要将两端的权重相加，并插入它们的和。