Basic Path and Distance Calculations in Graphs

Graphs are one of the most useful structures in mathematics and computer science for representing relationships between objects. A graph can describe roads connecting cities, links between web pages, communication networks, or connections between people in a social network. Once a graph is created, one of the most important questions we can ask is: How can we move from one point to another, and how far is that journey?

The concepts of paths and distances provide the foundation for answering these questions. A path describes a sequence of vertices connected by edges, while the distance between two vertices tells us the length of the shortest path connecting them. These ideas are simple at the basic level, but they are also the foundation of important algorithms used in navigation systems, network routing, artificial intelligence, and many other areas of computer science.

This article explains the basic concepts of paths and distance calculations in graphs, including vertices, edges, path length, shortest paths, weighted graphs, and common methods for calculating distances.

What Is a Graph?

A graph is a mathematical structure used to represent relationships between different objects. The objects are represented by vertices, also called nodes, and the relationships between them are represented by edges.

For example, imagine four cities: A, B, C, and D. If roads connect A to B, B to C, and C to D, these cities can be represented as vertices and the roads as edges.

A graph can be written using two basic components:

Text block:

Graph = (V, E)

Here, V represents the set of vertices and E represents the set of edges.

Graphs can be directed or undirected. In an undirected graph, movement along an edge is possible in both directions. In a directed graph, an edge has a specific direction, so movement may be possible from one vertex to another but not necessarily back.

Graphs can also be weighted or unweighted. In an unweighted graph, every edge is normally treated as having the same length or cost. In a weighted graph, each edge can have a different value representing distance, time, cost, or another measurement.

What Is a Path in a Graph?

A path is a sequence of vertices in which each consecutive pair of vertices is connected by an edge.

Suppose a graph contains the following connections:

A path from A to D can be written as:

A → B → C → D

This path shows that we start at vertex A, move to B, then C, and finally reach D.

The important point is that every movement from one vertex to the next must follow an existing edge in the graph.

A path can contain two vertices or many vertices, depending on the structure of the graph.

What Is the Length of a Path?

The length of a path depends on whether the graph is weighted or unweighted.

In an unweighted graph, the path length is usually the number of edges used.

For example:

A → B → C → D

This path contains three edges:

Therefore, its length is 3.

Text block:

Path length = Number of edges in the path

For a weighted graph, the length of a path is calculated by adding the weights of all edges used.

Suppose:

Then the total path length is:

Text block:

Path length = 4 + 7 + 3 = 14

The path therefore has a total weight of 14.

What Is Distance Between Two Vertices?

The distance between two vertices is generally defined as the length of the shortest path connecting them.

This is an important distinction. A graph may contain several different paths between the same two vertices, but the distance is based on the shortest one.

For example, suppose there are two ways to travel from A to D:

Path 1:

A → B → D

with a total length of 8.

Path 2:

A → C → E → D

with a total length of 12.

The distance from A to D is 8 because the first path is shorter.

Text block:

Distance(A, D) = Shortest path length from A to D

This concept is fundamental to shortest-path problems in graph theory and computer science.

Distance in an Unweighted Graph

In an unweighted graph, each edge is normally considered to have a length of 1.

Consider the graph:

A — B — C — D

To travel from A to D, we use three edges.

Therefore:

Text block:

Distance(A, D) = 3

Now consider another path:

A — E — D

This path contains only two edges.

Therefore:

Text block:

Distance(A, D) = 2

If both paths exist, the distance is 2 because it is the smaller number of edges.

This type of distance is sometimes called hop distance, because each edge represents one hop from one vertex to another.

Distance in a Weighted Graph

In a weighted graph, edges have different weights. These weights can represent physical distance, travel time, financial cost, energy consumption, or another quantity.

For example:

There are two possible ways to reach B from A.

The first path is:

A → B

Its total weight is 5.

The second path is:

A → C → B

Its total weight is:

Text block:

2 + 1 = 3

Therefore, the shortest distance from A to B is 3.

Text block:

Distance(A, B) = 3

Even though there is a direct edge from A to B, it is not necessarily the shortest route. This is one of the most important ideas to understand when working with weighted graphs.

Direct Distance and Shortest Distance

A direct edge between two vertices does not always provide the shortest path.

Consider this example:

The direct route from A to B has a weight of 10.

However, going through C gives:

Text block:

A → C → B = 3 + 2 = 5

Therefore:

Text block:

Shortest distance from A to B = 5

This example shows why graph algorithms often need to examine multiple possible paths instead of simply choosing a direct connection.

How to Calculate the Length of a Path

Calculating path length is straightforward.

Step 1: Identify the Path

First, identify the sequence of vertices being used.

For example:

A → B → C → D

Step 2: Identify the Edge Values

Suppose the edge weights are:

Step 3: Add the Weights

Add all the edge weights along the selected path.

Text block:

Path length = 6 + 4 + 5 = 15

Therefore, the length of the path is 15.

In an unweighted graph, you simply count the number of edges instead of adding numerical weights.

Finding the Shortest Path

Finding the shortest path means determining the path with the smallest total length or weight between two vertices.

Suppose there are three possible routes from A to D:

Path 1:

A → B → D

Length = 9

Path 2:

A → C → D

Length = 6

Path 3:

A → E → F → D

Length = 11

The shortest path is Path 2.

Text block:

Shortest distance = min(9, 6, 11) = 6

Therefore:

Text block:

Shortest path = A → C → D

Shortest distance = 6

The min idea is important because shortest-path calculations essentially compare possible route lengths and select the smallest valid value.

Distance Between Multiple Vertices

Sometimes we need to find the distance from one starting vertex to every other vertex in the graph.

For example, suppose A is the starting point.

The graph may have distances such as:

These values provide a distance relationship between the starting vertex and the remaining vertices.

In computer science, calculating distances from one starting vertex to many other vertices is a common graph problem. It is useful in navigation, network analysis, and routing systems.

Breadth-First Search and Distance

For an unweighted graph, Breadth-First Search (BFS) is commonly used to find the shortest distance from a starting vertex.

BFS explores vertices level by level.

Suppose we start from A.

At distance 0:

A

At distance 1:

B, C

At distance 2:

D, E

At distance 3:

F

This means:

Text block:

Because BFS visits vertices in increasing order of their number of edges from the starting point, the first time it reaches a vertex in an unweighted graph, it has found a shortest path to that vertex.

Weighted Graphs and Shortest-Path Algorithms

For weighted graphs, simply counting edges is not enough because different edges can have different costs.

Several algorithms are commonly used for shortest-path calculations.

Dijkstra’s algorithm is widely used when edge weights are non-negative. It repeatedly selects the currently closest unvisited vertex and uses it to improve distances to neighboring vertices.

Bellman-Ford algorithm can handle graphs with negative edge weights and can also detect certain negative-weight cycles.

Floyd-Warshall algorithm is useful for finding shortest distances between many pairs of vertices.

At the basic level, however, the central idea remains the same: calculate possible path costs and determine the smallest valid distance.

What Is a Shortest Path Tree?

When we calculate the shortest distances from one starting vertex to other vertices, we can also record which previous vertex produced the shortest route.

These connections can form a shortest path tree.

For example, suppose the shortest routes from A are:

The corresponding tree shows how each vertex can be reached through its shortest known route from A.

A shortest path tree is useful because it stores more than just the distance. It also helps reconstruct the actual route.

Distance and Path Are Not the Same

It is important to distinguish between a path and a distance.

A path describes the route itself.

A distance describes the length or total cost of that route, usually using the shortest available path.

For example:

A → B → C → D

is a path.

If its total weight is 12, then 12 is the length of that path.

If another path from A to D has a weight of 9, then the distance from A to D is 9.

Text block:

Path = Sequence of connected vertices

Path length = Total number of edges or total edge weight

Distance = Length of the shortest path

Keeping these three ideas separate makes graph problems much easier to understand.

Real-World Applications of Path and Distance Calculations

Path and distance calculations are not limited to textbook graph problems. They are used in many real-world systems.

Navigation Systems

Road maps can be represented as weighted graphs. Locations are vertices, while roads are edges. The weights can represent distances or travel times.

A navigation system can then search for a suitable route between two locations.

Computer Networks

In a computer network, computers, routers, and other devices can be represented as vertices. Network connections are represented as edges.

Distance or cost can represent latency, bandwidth-related cost, or the number of network hops.

Social Networks

People can be represented as vertices and relationships as edges. The distance between two people can represent how many connection steps separate them.

For example, if A is directly connected to B and B is connected to C, then C is two steps away from A.

Web Search and Recommendation Systems

Connections between pages, products, users, or other objects can be modeled using graphs. Graph-based distance and path calculations can help analyze relationships and discover connections.

Robotics

A robot moving through an environment can treat possible locations as vertices and possible movements as edges. The weights can represent movement distance, energy consumption, or time.

The robot can then search for a suitable route to its destination.

Common Mistakes When Calculating Graph Distance

Beginners often make a few common mistakes when working with paths and distances.

One mistake is assuming that the direct edge always provides the shortest route. As we saw earlier, a route through several vertices can sometimes have a smaller total weight.

Another mistake is confusing the number of vertices with the number of edges. For example:

A → B → C → D

contains four vertices but only three edges.

Therefore, in an unweighted graph, the path length is 3, not 4.

A third mistake is adding weights from edges that are not actually part of the selected path. Only the edges used by the path should be included in the calculation.

Finally, in a weighted graph, choosing the path with the fewest edges does not necessarily give the shortest distance. The edge weights must be considered.

Summary of Important Formulas

The most basic formulas for path and distance calculations can be summarized as follows.

Text block:

Unweighted path length = Number of edges in the path

Weighted path length = Sum of the weights of all edges in the path

Distance between two vertices = Length of the shortest path between them

Shortest distance = Minimum value among all valid path lengths

For an unweighted graph:

Text block:

Distance(u, v) = Minimum number of edges required to travel from u to v

For a weighted graph:

Text block:

Distance(u, v) = Minimum total edge weight among all paths from u to v

These formulas provide the basic mathematical foundation for understanding shortest-path problems.

Conclusion

Path and distance calculations are fundamental concepts in graph theory and computer science. A path describes how we move from one vertex to another, while its length measures the number of edges or the total weight of those edges. The distance between two vertices is normally the length of the shortest available path.

In unweighted graphs, distance can often be found by counting edges, and BFS provides an efficient way to calculate shortest distances from a starting vertex. In weighted graphs, edge values must be added for each possible route, and specialized algorithms such as Dijkstra’s algorithm can be used for appropriate types of graphs.

Understanding these basic ideas creates a strong foundation for more advanced topics such as shortest-path algorithms, graph traversal, network optimization, routing, and graph-based problem solving. Once paths and distances become familiar, many real-world problems involving routes, connections, and networks become much easier to represent and solve.