From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
	ip-172-31-74-118.ec2.internal
X-Spam-Level: *
X-Spam-Status: No, score=1.8 required=3.0 tests=BAYES_50,FORGED_GMAIL_RCVD,
	FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.6
Path: eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: =?UTF-8?Q?Bj=c3=b6rn_Lundin?= <b.f.lundin@gmail.com>
Newsgroups: comp.lang.ada
Subject: Dijkstra and graphs
Date: Thu, 26 Aug 2021 14:26:23 +0200
Organization: A noiseless patient Spider
Message-ID: <sg819f$lj1$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 26 Aug 2021 12:26:23 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="a3c54ae614c70792a8054f76ccc06b60";
	logging-data="22113"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18+dBo5LRdEfQpbnT4n14ML"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:78.0)
 Gecko/20100101 Thunderbird/78.13.0
Cancel-Lock: sha1:Si/lR3mIZDs835fwLJnEPVEnHPQ=
Content-Language: en-US
X-Mozilla-News-Host: snews://news.eternal-september.org:563
Xref: reader02.eternal-september.org comp.lang.ada:62543
List-Id: <comp.lang.ada>

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