# Edge-weighted graph

An edge-weighted graph , weighted graph for short , is a graph in graph theory in which a real number is assigned as the edge weight to each edge . Edge-weighted graphs can be directed or undirected. A graph whose nodes are weighted is called a node-weighted graph .

## Weight functions

Edge weights are generally given by an edge weight function. One such weight function is a mapping of the shape

${\ displaystyle d \ colon E \ to \ mathbb {R}}$,

which assigns a real number as weight to each edge . The edge weight of an edge is then denoted by or . ${\ displaystyle e \ in E}$${\ displaystyle d (e)}$${\ displaystyle d_ {e}}$

## Metric graph

A complete edge-weighted graph is called metric if for all nodes of the graph ${\ displaystyle a, b, c}$

${\ displaystyle d ({a, c}) \ leq d ({a, b}) + d ({b, c})}$

applies. This means that the route from via to must not be cheaper than the direct route from to . An example of metric graphs distance graphs . ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle a}$${\ displaystyle c}$

## Applications

For many graph-theoretic problems, additional parameters are required, for example a cost function for determining shortest paths or a capacity function for determining maximum flows . In such a case, a problem instance is often described by a tuple of the form which, in addition to the graph, contains the desired weight function. ${\ displaystyle (G, d)}$