Weighted graph

Basic definitions and examples

Recall that a graph is a set of nodes and edges, where each edge represents a connection between two nodes. A weighted graph is a graph where each edge has a numerical value called a weight. Given below is an example of a weighted graph:

The graph consists of five nodes and seven edges (each has a weight). For example, the edge $\{0, 3\}$ has the weight $7$, the edge $\{1, 2\}$ has the weight $1$.

Weighted graphs are often used to model real objects and relationships between nodes. The above example can be considered as a part of Google maps, where the nodes are cities and the edges are roads. The weight of each edge is the time/distance between two cities.

The above example is a weighted undirected graph with undirected edges. But weighted graphs can also be directed. Given below is an example of a directed weighted graph:

Weighted directed graphs can also be used to model some real processes. For instance, the node $0$ in the example above can be considered as a storage place, from where we need to transfer some resources to the destination point, say to the node $2$. The remaining nodes can be considered as intermediate places. Each edge shows a direction in which the resources can be transferred. The weight of an edge shows the maximum amount of resources that can be sent through it.

Note that for the example above all the weights are positive, but negative and zero weights are also allowed.

A representation of weighted graphs

An unweighted graph can be represented using an adjacency matrix or an adjacency list. A weighted graph can also be represented using both of these structures.

For a weighted graph with $n$ nodes, an adjacency matrix is a $n \times n$ matrix $A$, where $A[i, j]$ is the weight of an edge between adjacent nodes $i$ and $j$. If there is no edge between $i$ and $j$, the corresponding value is set to $\infty$. The diagonal elements of the matrix are assigned to $0$ (here we assume that there are no self-loops in a graph). For the directed one above, an adjacency matrix is the following:

The first row and column of the matrix correspond to the nodes of the graph. The remaining cells correspond to the weights. For example, $A[1, 3] =4$ since there is an edge from node $1$ to node $3$ with the weight $4$. $A[3, 1] = \infty$ since there is no edge from node $3$ to node $1$.

Adjacency lists for weighted and unweighted graphs are similar. The only difference is that we need to store an additional value in each node of a list corresponding to the weight of an edge. For the directed graph above, an adjacency list looks like this:

Each node of the list contains a pair of values. The first value is the label of a node of the graph, the second one is the weight of the corresponding edge. For example, the first node in the first list corresponds to the edge $\{0, 1\}$ that has the weight $3$. The second node in the same list corresponds to the edge $\{0, 3\}$ that has the weight $7$. Since the node $2$ of the graph has no neighbors, the corresponding list of neighbors is empty.

Paths in weighted graphs

A path in a weighted graph is the same as in an unweighted one. The only difference is that in a weighted graph a path has a weight that is equal to the sum of the edge weights in the path. For example, consider a path $0 \to 4 \to 3 \to 2$ (shown in blue) for a directed graph:

The path consists of three edges. The total weight of the path is the sum of their weights: $8 + 3 + 2 = 13$. One may note that there is another path from the node $0$ to the node $2$: $0 \to 1 \to 2$ (shown in red):

The weight of the path is $3 + 1 = 4$ , which is less than the weight of the blue path.

The problem of finding the shortest path (a path with the minimum weight) between two nodes in a graph often arises in programming practice. There are several algorithms solving the shortest path problem. We will consider them in more detail in the next topics.