I can not understand where the values ​​of the weight of the ribs in the examples of the Dijkstra algorithm come from. When from the initial vertex S (the shortest path is zero, there are no preceding vertices) to the nearest vertices t and у weight of the edges is 6 and 4, respectively ... it is not clear to me where these values ​​come from? Is this an arbitrary distance (or time) or are they somehow determined?

  • If you have no scales in the task (all edges are equivalent), then consider their weights equal to one. Or any other, but positive and equal for all edges, value. On the other hand, if the edge weights are not specified, then it is more reasonable to use a simpler, for example, wave algorithm. - Akina
  • In real life, the weight will be the real distance along a given road, or the time it takes to travel along it, or some other physical quantity that affects the profitability of the path in the graph. And if this is just an abstract task for the compilation of the algorithm, then these numbers are taken absolutely from there from where and in the task "Vasya had 6 apples, and Masha had 4 apples, how many apples did Vasya have with Masha", i.e. practically from the ceiling - Mike

2 answers 2

In fact, Dijkstra's algorithm works for a weighted graph with non-negative edge weights.

Naturally, in a weighted graph, each edge has its own weight. So these values ​​of the weights of the ribs are not "taken from somewhere", but are integral properties of the graph. In this case, the graph used (rather arbitrarily) as an example for the Dijkstra algorithm.

Those. in a certain sense, they are arbitrary - but only in the sense that another graph could be used as an example, with different edge weights ...

I will add in response to the addition of the comment:

Imagine that you need to tell the student about multiplying in a bar. You tell how the discharges are transferred, how the numbers multiply ... Speak - multiply, for example, 123 by 456.
And he asks you - I do not understand, where, when multiplying, do these 3 * 6 come from first? Are they arbitrary or not?
How do you answer? On the one hand, they seem to be arbitrary, but on the other - they are there only because you have already chosen 123 * 456 as an example, and therefore they simply have to be there - 3 and 6. Because (arbitrarily) 123 and 456.
You can choose other numbers, say, 327 and 658, and start by multiplying 7 by 8, but you cannot, by choosing 123 and 456, multiply 7 by 8 ...
So clearer?

  • I already knew that, I cannot understand an example in which arbitrary values ​​are taken .. And you write it seems they are arbitrary, but it seems to be a property of the Dijkstra algorithm ... I still don’t understand - ZdraviSmisl
  • one
    Imagine that you need to tell the student about multiplying in a bar. You tell how the discharges are transferred, how the numbers multiply ... Speak - let's multiply, for example, 123 by 456. And he asks you - I don't understand, where do these 3 * 6 come from when multiplying at the beginning? Are they arbitrary or not? How do you answer? On the one hand, they seem to be arbitrary, but on the other, they are there because you have already chosen 123 * 456, and therefore they simply have to be there - 3 and 6, because 123 and 456 are chosen (arbitrarily). You can choose 327 by 658, but you cannot, by choosing 123 and 456, multiply 7 by 8 ... Is that clearer? - Harry
  • one
    Perhaps it would be clearer. You have a weighted graph (in reality, these may be: cities with roads (km or hours), planets with A. e., Computers and access / data transfer times), etc.). And here the algorithm is applied to this graph. Weights should already be, this is an input parameter. The algorithm only uses them. As you were given an example above: f (x, y) = (something), x, y are input parameters, as in multiplication, addition, etc. - Dejsving
  • Yes, thanks to everyone .. now more clear) - ZdraviSmisl

I suppose you mean what structure is responsible for setting the length of the edges. If so, then the weight of the edges is given in the adjacency table.

In it, the number of columns and rows is equal to the number of vertices. Cell (a, b) contains the path (Its length or cost) from a to b. If it is impossible to pass, they usually put some high constant value, which conditionally is taken for infinity (the Infinite path -> it is impossible to pass).

Usually this is the maximum number of the type divided by two, so that when adding you do not fall into the negative range and do not find the wrong path.