A weighted graph is a type of graph in which each edge is assigned a numerical value, called a weight. These weights can represent various quantities, such as distances, costs, time, or any other relevant measure associated with the edges. The weights are used to provide additional information about the relationships between the vertices in the graph.
Formally, a weighted graph G is defined by a set of vertices V, a set of edges E, and a function w:E→R that assigns a weight to each edge. The function w maps each edge to a real number, indicating the weight of that edge.
Weighted graphs are particularly useful in modeling real-world scenarios where the relationships between entities have associated numerical values. For example:
-
Networks: In transportation networks, the weights could represent distances between locations or travel times along edges.
-
Financial networks: In financial systems, the weights might represent transaction costs or the amount of capital flow between entities.
-
Communication networks: In communication networks, the weights could represent the delay or cost associated with transmitting data between nodes.
Several algorithms and problems involve weighted graphs, such as finding the shortest path between two vertices, determining minimum spanning trees, and solving optimization problems related to network flows. Common algorithms for weighted graphs include Dijkstra's algorithm for finding the shortest path and Prim's algorithm for finding the minimum spanning tree.
