加权图 定义为一种特殊的图，在这种图中，每条边都被分配了权重，这些权重可以代表成本、距离以及许多其他相关的计量单位。
!加权图示例加权图示例
加权图的应用：
- 2D 矩阵游戏： 在二维矩阵中，我们可以利用它来找到从起点到终点具有最大和的最优路径，及其许多变体，这些在网上都能找到。
- 生成树： 加权图用于从图中寻找最小生成树，这描绘了遍历图中所有节点的最小成本。
- 约束图： 图常用于表示项目之间的约束关系。应用于调度、产品设计、资产分配、电路设计和人工智能等领域。
- 依赖图： 有向加权图可用于表示项目之间的依赖关系或优先顺序。我们可以分配优先级来制定一种流程，以便我们在解决问题时按照从最高优先级到最低优先级的顺序遍历图。这类图常用于大型项目中，以此规划哪些组件依赖于其他组件，并旨在遵守依赖关系的同时，最小化完成项目的总时间或成本。
- 编译器： 加权图在编译器中被广泛使用。它们可用于类型推断、所谓的“数据流分析”，以及许多其他目的，例如数据库语言中的查询优化。
- 人工智能： 加权图用于人工智能中的决策过程，例如在游戏树中用于确定游戏中的最佳一步。
- 图像处理： 加权图用于图像处理中的分割，其中边的权重代表两个像素之间的相似度。
- 自然语言处理： 加权图用于自然语言处理中的文本分类，其中边的权重代表两个词之间的相似度。
加权图的实时应用：
- 交通网络： 使用加权图，我们可以计算出耗时最少的路径，或总距离最短的路径。这只是加权图用于更复杂系统（如 GPS 系统）的一个简化示例。许多大型科技公司（如 OLA、UBER、RAPIDO 等）使用图来研究交通模式、红绿灯时长等。许多地图程序（如 Google Maps、Bing Maps 等）也使用图网络。
- 文档链接图： 链接加权图用于分析网页的相关性、最佳信息来源和优质链接站点，方法是将查看次数作为图中的权重进行统计。
- 流行病学： 加权图可用于计算传染病患者从感染者传播给健康者的最大距离（传播范围）。
- 量子场论中的图： 顶点代表量子系统的状态，边代表状态之间的转换。这些图可用于分析路径积分，将它们加起来会生成量子振幅。我们可以使用加权图来研究寻找沿路径的最大频率。
- 社交网络图： 我们可以找出哪些用户在网络中是直接连接（直接连接）或间接连接（间接连接）的。但现在加权图也用于社交媒体的许多目的，例如，最近 Instagram 正在使用“密友” 这样的功能，这与所有好友并不相同，这些功能正是通过加权图实现的。
- 网络数据包流量图： 网络数据包流量图用于分析网络安全、研究蠕虫传播以及跟踪犯罪或非犯罪活动。
加权图的优势：
- 更好地表现现实场景： 加权图能更准确地表现许多现实场景，在这些场景中，实体之间的关系具有不同程度的重要性。例如，在道路网络中，某些道路可能限速更高或车道更多，这些差异可以通过权重来表示。
- 更准确的寻路： 在加权图中，寻找两个节点之间的最短路径时会考虑边的权重，这可以带来更准确的结果。这在寻找最优路径至关重要的应用中特别有用，例如物流或运输规划。
- 更高效的算法： 许多图算法在应用于加权图时更为高效，例如用于寻找最短路径的 Dijkstra 算法。这是因为权重提供了额外的信息，可用于优化搜索过程。
- 更灵活的分析： 加权图允许我们对节点之间的关系进行更灵活的分析，因为权重可以量化关系的强度、距离或成本。