find the shortest path between two shapes

Started by cliff50, September 06, 2020, 04:41:29 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

wapperdude

Yes.  Green is shortest path.
Yellow are the immediate paths from the starting node.
No, there is no inherent limit coded in.  Whatever tops out will be for "outside" reasons.

Generally, yes.  But, it only visits each path once.  It is based upon Dijkstra's algorithm.  The original link provides more detail, and the code actually has a lot of comments.

The bail-out, only occurs if you select either incoming or outgoing paths, which implies a specific direction.  If there's no way to get to the destination, then result is zero paths of the type selected will get you to Rome.
Visio 2019 Pro

cliff50

#16
Wapperdude  ... for the minute your solution is fit for purpose  ... (purpose being MPLS network evaluation tool).

I am unsure though ... why you went the extra mile  and include directional capability.  Perhaps this could be a model of street navigation (one way streets etc).

you must have been thinking outside the box  ;)

~ cheers
Cliff

wapperdude

Just seemed like the right thing to do.  Another application could also be electronic circuits:  fundamentally, outputs drive inputs.  So, that's an exploitable feature.   Visio also has an unsung feature, the D-cell, for connection points.  That can be utilized to distinguish types of i/o:  inputs, outputs, tri-state, power, etc.

Visio 2019 Pro

cliff50

Wapperdude ...  I realized the yellow coloration is crucial  to a consistent outcome.  I am unsure if the distancing calculation is incorporated into the outcome in any way ... it appears not .. but I will follow the "yellow brick road"

wapperdude

Colored paths have secondary purpose... they indicate when a path has been counted.  The algorithm is based upon single traverse.
Visio 2019 Pro

Surrogate


cliff50

#21
modified version of wapperdudes solution.
my study of MPLS reveals there needs to be  conditional filters attached to the algorithm to determine if a physical path en route is available.
The filters are dedicated to resolving the following :
Bandwidth , Load balancing , or availability ( network impacts).

The directional component of the links in the original solution are not necessary in the study.
I feel the "logical" assignment of bandwidth on the physical links are mission critical for designing these type of networks.
work in progress.
cheers
Cliff

Nikolay

#22
Quote from: Surrogate on December 16, 2020, 08:47:58 AM
few days ago i find this demo by Cliff A.

Just wondering why this video about finding shortest paths is marked 18+ ?! You have to verify your age to watch it. Well, I did and watched it to the end, but there are just lines, circles and rectangles. Am I missing something? ;D ;D ;D

cliff50

#23
Nikolay,
I am no expert on posting youtube.(hence button +18).

The video is a demonstration of MPLS (multi path label switching) style of Network , using the developer version of Visio (professional).

From a transmission/network/bandwidth perspective the following abstract applies:
Evolution of topology PDH -> SDH-> MPLS.

PDH linear by nature, its bandwidth could be readily drawn on paper.
SDH non  linear, its bandwidth is "static" and configurable. When a link is impacted, alternate routing paths pre configured by human hand.
MPLS non linear , its bandwidth is dynamic . Alternate bandwidth is automatically configured using an algorithm based upon shortest path(least number of nodes).

The algorithm is very similar to Dijkstra's shortest path algorithm.

Regards the image interpretation.
the circles ostensibly represent Routers, the lines represent the physical connections between the routers. ( transmission links)
the numbers on the line represent how much bandwidth is spare on the link.

regards the audience.
a demonstration to show the possibilities, using the Visio platform, issues of MPLS bandwidth design and control.

any feedback appreciated.

regards
Cliff A.

Nikolay

#24
Dear Cliff, thank you for clarifying.
What I meant is that the video may be simply not accessible to most people because not everyone would go through age verification Now you see blank screen and "age verification required" button (with credit card or photo document). 18+ video usually means "adult" (porn) content, therefore it may be positioned incorrectly by youtube. "Only circles and rectangles" was meant merely as as a joke referring to "adult video" category, sorry.

cliff50

#25
Hi Nikolay,

Please, no need to apologize , I am the one in error. I didn't realize\ understand the consequences of the restriction 18 +
Thanks to your prudent observation -> I have amended the status.  update-> https://youtu.be/znFO-PDOCp0

I really appreciate your and your fellow Visio artisans, contributions to this forum.

best wishes for the Christmas season Sir.
Cliff  :)