In previous discussions natural numbers have been assigned to objects to identify them. Assigning integer-names to the links between linked objects could be done (the computer invisibly does this) but it is not done openly in discussions. However, discussions in this section involve numbers attached to links. These numbers are not for identification, but come with the graph, such as shown in adjacent Fig A. The reader may assign integer-names to the objects, but should not change any of the numbers attached to the links. In this section these numbers are always positive (never negative nor zero). For simplicity they are natural numbers here, but in reality they may be positive real numbers. In any case, the numbers are called weights" assigned to the links. The graph is called graph with weighted links or simply graph with weights. In such graphs all links have been assigned weights. All graphs with weights will be connected.
One example of graphs with weights are cities with roads connecting them. Roads have lengths and give a type of distance between the cities. In graph theory, the cities are objects, roads are links and numbers are somehow attached to the links to give lengths. Interpreting the numbers as lengths of links is so easily understood and natural that weights may also be called the lengths of the links. This is equivalent to saying that the numbers represent distances between between adjacent objects. However, drawings need not be drawn to scale, yet can still give correct information if the numbers are retained on all the links.
In Fig B, the objects have been given integer-names. The short adjacency array for this graph without the weights is:
A practical and very understandable application of graphs with positive weights can now be given. Let weights attached to links have the meanings of lengths of those links. Then every path in the graph has a length. Simply add up the lengths of all the links in the path.
(It will be convenient to have paths of lengths zero. A path of lenth zero means that the path connects two coincident objects, and the path contains no other objects.) A fundamental task in graph theory is: in a connected graph with weights find a shortest path between two given objects (there may be more than one shortest path). In Fig B, there are many paths connecting objects 1 and 7. Some are as follows.
Path 1-4-6-8-7 has length 2+11+8+7=28
Path 1-3-8-7 has length 5+13+7=25
Path 1-5-7 has length 12+6=18
A computer program accepting (&&) as data finds a shortest path to be
path 1-2-5-7 with length 4+1+6=11
Actually the program finds shortest paths between object 1 and each of the other objects in the graph. In doing that, it determines a spanning tree with root at the left-most object as shown in Fig C. This figure indicates that the shortest paths and the spanning tree are independent of the labels (integer-names) assigned to the objects.