Hi,
I'm looking to update myself on graphs a bit while I
have a problem at hand that would benefit from Dijkstra's traveling
salesman problem.

The problem at hand is a large conveyor system at a warehouse.
The PLC will scan a box and tell me "box-id 123 is here, should I go
straight or divert'

I know the final destination of the box. So I'll look it up and say
'turn first right here' and the box diverts to the second lane on the
right. It then keeps going until it is scanned again and the procedure
repeats.

e-------f
| |
a------B-------C-----d
| |
g-------h

Box 1 starts at a - final destination is d
Scanners at B and C
Box 1 scanned at B 'go straight'
Here I'd like to increase weight B->C

Box 2 starts at a - final destination is d
Box 2 scanned at B 'go left' - since B->C has become more expensive
Here I'd like to increase weight B->e

Box 1 scanned at C 'go straight'
Here I'd like to decrease weight B->C

Box 3 starts at a - final destination is d
Box 3 scanned at B 'go straight' - since this is cheapest route again,
now when box 1 has left the area
Here I'd like to increase weight B->C because of box 3

You get the idea.

I have one solution (not handling this congestion) but I think I'd like
to look closer at Dijkstra. It has some advantages I like - like easy to
configure. Current solution will gt messy with hundreds of vertexes.

There is one implementation at
https://rosettacode.org/wiki/Dijkstra%27s_algorithm#Ada

which does basically what I want.

However - I cannot see what to add for me to update the weight in the
Edge array.

This implementation takes the weight between two locations or vertexes.
But this is static.

The more boxes between two locations the less I'd like to use that route.

In other words I'd like to dynamically change the weights.

Any hints ?

--
Björn

On 2021-08-26 14:26, Björn Lundin wrote:

> In other words I'd like to dynamically change the weights.

Usually implementations of weighted graphs order outgoing edges
according to their weights. E.g.

http://www.dmitry-kazakov.de/ada/components.htm#Generic_Directed_Weighted_Graph

Because you want to search edges by weights efficiently. So, changing
weight is not possible. Though you always can remove the edge and add it
again with another weight.

Alternatively, if you are OK with linear search, you simply take a
directed graph and add an array of weights indexed by the child number
to each node.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Den 2021-08-26 kl. 14:48, skrev Dmitry A. Kazakov:
> On 2021-08-26 14:26, Björn Lundin wrote:
>
>> In other words I'd like to dynamically change the weights.
>
>Though you always can remove the edge and add it
> again with another weight.
>

OK - I'll look into that path

thanks

--
Björn