comp.lang.ada
 help / color / mirror / Atom feed
* Dijkstra and graphs
@ 2021-08-26 12:26 Björn Lundin
  2021-08-26 12:48 ` Dmitry A. Kazakov
  0 siblings, 1 reply; 3+ messages in thread
From: Björn Lundin @ 2021-08-26 12:26 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: Dijkstra and graphs
  2021-08-26 12:26 Dijkstra and graphs Björn Lundin
@ 2021-08-26 12:48 ` Dmitry A. Kazakov
  2021-08-26 14:10   ` Björn Lundin
  0 siblings, 1 reply; 3+ messages in thread
From: Dmitry A. Kazakov @ 2021-08-26 12:48 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: Dijkstra and graphs
  2021-08-26 12:48 ` Dmitry A. Kazakov
@ 2021-08-26 14:10   ` Björn Lundin
  0 siblings, 0 replies; 3+ messages in thread
From: Björn Lundin @ 2021-08-26 14:10 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2021-08-26 14:10 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-08-26 12:26 Dijkstra and graphs Björn Lundin
2021-08-26 12:48 ` Dmitry A. Kazakov
2021-08-26 14:10   ` Björn Lundin

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox