LOOK INSIDE
An efficient algorithm to find the shortest path between two nodes within a network of any size.
Three versions, all using the same approach:
1. A “luxury” version with labels and named nodes.
2. A “bare bones” version taking numbered nodes and links as input.
3. A version that will find shortest paths from one node to all nodes.data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKAAAAB4CAYAAAB1ovlvAAAAAXNSR0IArs4c6QAAAERlWElmTU0AKgAAAAgAAYdpAAQAAAABAAAAGgAAAAAAA6ABAAMAAAABAAEAAKACAAQAAAABAAAAoKADAAQAAAABAAAAeAAAAAAeaS0RAAADM0lEQVR4Ae3XMUqcARSF0X9CrN2Cq3ENgo2FLsP1uBI3YytimahdIAZuuOEm5Ezn+HhvPH444+nb2+PwIDAS+DK66yyBDwEBCmEqIMApv+MC1MBUQIBTfscFqIGpgACn/I4LUANTAQFO+R0XoAamAgKc8jsuQA1MBQQ45XdcgBqYCghwyu+4ADUwFRDglN9xAWpgKiDAKb/jAtTAVECAU37HBaiBqYAAp/yOC1ADUwEBTvkdF6AGpgICnPI7LkANTAUEOOV3XIAamAoIcMrvuAA1MBUQ4JTfcQFqYCogwCm/4wLUwFRAgFN+xwWogamAAKf8jgtQA1MBAU75HRegBqYCApzyOy5ADUwFBDjld1yAGpgKCHDK77gANTAVEOCU33EBamAqIMApv+MC1MBUQIBTfscFqIGpgACn/I4LUANTga/T63/x8YeHh+P5+fm4vLw8Li4u/uJX+m+/tNO3t8e//SP8mVf/8vJy3N3dHa+vr8fT09NxfX19nE6n4/b29jg7O/szR//DrQL8xS/98fHxuL+/P87Pz3+Yeo/y5ubm47mrq6sfvueLTMBnwMzLdFnAX8BPQH/2Fvw++v627C34E7TfeFqAn6D5J+QTmPLTAiyDWpcJ+AyYeZkuCwiwDGpdJiDAzMt0WUCAZVDrMgEBZl6mywICLINalwkIMPMyXRYQYBnUukxAgJmX6bKAAMug1mUCAsy8TJcFBFgGtS4TEGDmZbosIMAyqHWZgAAzL9NlAQGWQa3LBASYeZkuCwiwDGpdJiDAzMt0WUCAZVDrMgEBZl6mywICLINalwkIMPMyXRYQYBnUukxAgJmX6bKAAMug1mUCAsy8TJcFBFgGtS4TEGDmZbosIMAyqHWZgAAzL9NlAQGWQa3LBASYeZkuCwiwDGpdJiDAzMt0WUCAZVDrMgEBZl6mywICLINalwkIMPMyXRYQYBnUukxAgJmX6bKAAMug1mUCAsy8TJcFBFgGtS4TEGDmZbosIMAyqHWZgAAzL9NlAQGWQa3LBASYeZkuCwiwDGpdJiDAzMt0WUCAZVDrMgEBZl6mywICLINalwkIMPMyXRYQYBnUukzgO7RmRdVFbOJYAAAAAElFTkSuQmCCLOOK INSIDE
An efficient algorithm to find the shortest path between two nodes within a network of any size.
Three versions, all using the same approach:
1. A “luxury” version with labels and named nodes.
2. A “bare bones” version taking numbered nodes and links as input.
3. A version that will find shortest paths from one node to all nodes.WHAT IT DOES: calculate the shortest distance through a network from one node to another node
INPUT:
1. list of unidirectional links: (("from" node) ("to" node) ("length" units), in any order)
2. label signifying “from” attribute within (1)
3. label signifying “to” attribute within (1)
4. label signifying “length” attribute within (1)
5, the node within the network where the route starts
6. the node within the network where the route ends
7. (upvar) returns the shortest route (list of links from origin through destination)
Nodes should be text, so numbers need a prefix (e.g. 23 -> n23)
ERRORS CAUGHT:
An error is raised if either the “origin” ot the “destination” node is not part of the network, or if there is no route through the network from origin to destination.
HOW: Dijkstra's algorithmfromtolengthnodestentative distance010stopsnodelinkIdentify all nodes within the networkitemcheck if origin and destination are part of the networkunvisited nodes1simple list of nodes to which the shortest distance is yet unknownsorted linkscurrent node10minimum working distancetentative distancenodecurrent nodetentative distancenodeSelect the active node with the shortest distance from the origin. No shorter route can be found, so routes to this node need not be tried any more.each loop is one generation of shorter routestentative distance10routestopstentative distanceWHAT IT DOES: calculate the shortest distance through a network from one node to another node
INPUT:
1. list of unidirectional links: (node-from, node-to, length) (NETWORK)
2. the node within the network where the route starts (ORIGIN)
3. the node within the network where the route ends (DESTINATION)
4. An indicator as to if the exactbroute must be made avaiable ad well as the shortest distance.
Nodes must be positive integers 1..n.
OUTPUT: Route (upvar) ia list of nodes along the shortest route, origin and destination included.
ERRORS CAUGHT:
An error is raised if there is no route through the network from origin to destination.
HOW: Dijkstra's algorithm.falselinks group1current nodeCurrent node is the unvisited node with the smallest distance.current index10Current node has now been visited.# unvisited-1unvisited distancesSelect new “current” node (next 4 blocks)minimum distancecurrent indexcurrent node10routeThrow an error.
Makes a red halo appear around the script that runs it,
with the input text shown in a speech balloon next to
the script, just like any Snap! error.
This is useful to put in the second script of SAFELY TRY
after some other instructions to undo the partial work of
the first script.pt:lança o erro _
pt:o agrupamento dos itens de _ de acordo com _
ca:$flash agrupa _ per _
WHAT IT DOES: calculate the shortest distances through a network from one node to all nodes.
INPUT:
1. list of unidirectional links: (node-from, node-to, length) (NETWORK)
2. the node within the network where the route starts (ORIGIN)
3. an indicator as to if the routes should be made vilavle as well as the distances.
Nodes must be positive integers 1..n.
OUTPUT: Routes (upvar) ia list of lists of nodes along the shortest route, origin and destinations included.
HOW: Dijkstra's algorithm.falselinks group1current nodeCurrent node is the unvisited node with the smallest distance.current index101Current node has now been visited.# unvisited-1unvisited distancesSelect new “current” node (next 4 blocks)minimum distancecurrent indexcurrent nodedata:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAeAAAAFoCAYAAACPNyggAAAAAXNSR0IArs4c6QAAAERlWElmTU0AKgAAAAgAAYdpAAQAAAABAAAAGgAAAAAAA6ABAAMAAAABAAEAAKACAAQAAAABAAAB4KADAAQAAAABAAABaAAAAAAHwbojAAAL30lEQVR4Ae3QMQEAAADCoPVPbQwfiEBhwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGDBgwIABAwYMGPgMDI3+AAEeFvcCAAAAAElFTkSuQmCC