6
$\begingroup$

This question might be redundant but I want to verify my understanding further. Suppose I have this linear directed graph:

$$S \overset{2}{\to} A \overset{1}{\to} B \overset{3}{\to} E \overset{1}\to D.$$

Here, $S$ is the source, $D$ is the target, and numbers indicate to edge weight:

  1. When taking about shortest path, do we only count the number of edges? So in this example, shortest paths from $S$ to $D$ is 4.
  2. Thus, when taking about shortest distance, we find the sum of the edges weights. So in this example, shortest distance from $S$ to $D$ is 7.

The reason why I elaborate this question using example is that I've seen plently of answers when I google this question but it seems they treat the work path and distance in similar way which is counting the number of edges (hops).

$\endgroup$
2
$\begingroup$

If it is ambiguous (as in this case), a well-written text should indicate what it means. If it doesn't, you might have to guess. Sometimes people are sloppy or imprecise, or rely on you to infer what they mean from context. There's certainly no guarantee that people will use language the way you describe -- it's not a standard assumption you can make.

In a graph without weights on the edges, the situation is clear, and we will use "shortest path" to mean the path with the fewest edges, and use "distance" to mean the number of edges. In such a graph, the notion of number of edges and sum of edge weights coincides (since we assume each edge has weight 1), so there's no distinction to draw. Thus, in that situation, we'd use the two words similarly.

In a graph with weights (lengths) on the edges, the most common situation is probably to use "shortest" path to mean the path with the smallest sum of edge weights, and use "distance" to refer to the length (sum of edge weights) of the shortest path. In other words, when there are weights (lengths) on the edges, the most common situation is that we never refer to anything involving the number of edges on the path.

But sometimes we have a graph with weights (lengths) on the edges, and we want to talk about two different distance metrics: the number of edges on the path, and the sum of the weights on the edges on the path. Then it's anyone's guess what terminology people will use; I don't think there's any accepted standard. In this situation, I think you have to hope that the writer defines their terms, or try to infer their meaning from context.

$\endgroup$
2
$\begingroup$

Bottom line: the only way to know is to look at how the resource (e.g., book) you are reading defines these concepts.

Typically, when talking about a path, we mean just that, i.e., a sequence of arcs and vertices. Every path has a length, which is defined as the sum of the weights of its arcs. When we talk about distance, it is the shortest length of any path between two vertices. Here, if arcs have no weight, it can be assumed they all have weight 1. In other words, we can count the number of arcs as you say.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.