在图论中，边权是指将图中的边赋予数值属性的一种方法。这些数值可以表示距离、成本、时间等多种实际意义。通过引入边权，我们可以构建更复杂和真实的问题模型，并解决一系列优化问题，如最短路径、最小生成树等。
在无向图或有向图中，边权是连接两个顶点之间的属性值。通常用非负实数来表示，但也可以根据实际需要使用其他数值类型，例如整数或者浮点数。边权可以用来衡量路径的成本、距离或优先级等。
在有向图中，每条边都有一个方向。边权重的应用广泛存在于物流网络、电信网络等领域。例如，在物流运输过程中，从节点A到B的路径可能因为不同的路线而有不同的运输成本或时间。
假设有一个运输网络模型如下：
- A -> B: 100元/吨
- B -> C: 200元/吨
通过A -> B -> C这条路径的成本为300元/吨。
在无向图中，每条边没有明确的方向。边权重通常用于表示两点间的关系或距离，比如交通网络、社交网络等。
考虑一个城市之间的交通网络：
- A <-> B: 距离为50公里
- B <-> C: 距离为70公里
通过A -> B -> C这条路径的距离为120公里。
Dijkstra算法是一种经典的用于求解单源最短路径问题的方法，适用于边权非负的加权图。
给定一个加权图G = (V, E)，以及源节点s，Dijkstra算法可以找到从s到所有其他顶点的最短路径。
A*算法是一种启发式搜索算法，在图论中主要用于解决最短路径问题。它结合了代价估计函数f(n) = g(n) + h(n)，其中g(n)表示从起点到达节点n的实际成本，h(n)是节点n到目标点的估算成本。
考虑一个迷宫寻路的问题：
- 使用Dijkstra算法和A*算法进行路径规划。
- A*通过启发式信息（例如曼哈顿距离）来优化搜索过程。
Kruskal算法是一种用于求解最小生成树的经典方法，适用于边权无负值的加权图。
给定一个无向连通图G = (V, E)，以及其边集合E上的权重函数w。Kruskal算法的目标是找到包含所有节点且总权重最小的一棵生成树。
Prim算法也是一种用于求解最小生成树的方法，同样适用于边权无负值的加权图。
给定一个连通图G = (V, E)，以及其边集合E上的权重函数w。Prim算法从任意节点开始构建一棵最小生成树。
边权在图论中的应用非常广泛，不仅限于最短路径和最小生成树问题。在实际中，通过对图进行适当的加权处理，我们可以解决更多复杂的问题，并找到更加有效的解决方案。