1 Reply Latest reply on Apr 14, 2009 1:43 PM by wvxvw

# Write a recursive function to determine all possible paths between a number of addresses

Hi,

I have a matrix which holds the time data it takes to travel between different addresses (Zipcodes actually).

I want to determine all possible unique routes (each route should travel each zipcode), so I can than determine which routes take the least amount of time. I thought up the easiest solution to use a recursive function and determine all unique routes by mimicing a tree like structure with arrays.

However my ActionScript/Flex knowledge is not sufficient enough to write that up I'm afraid.

My begin scenario looks like this:

```var TimeMatrix:Array = {
"3014CD" : {
"1011AB" : 50,
"9714AM" : 30,
"2727"   : 20 }
"1011AB" : {
"3014CD" : 30,
"9714AM" : 40,
"2727"   : 10,
"9714AM" : {
"3014CD" : 55,
"1011AB" : 20,
"2727"   : 30 }
"2727" : {
"3014CD" : 78,
"1011AB" : 30,
"9714AM" : 25 }
};

var Zipcodes:Array;
Zipcodes.push("3014CD");
Zipcodes.push("1011AB");
Zipcodes.push("9714AM");
Zipcodes.push("2727");

```

Thanks in advance

• ###### 1. Re: Write a recursive function to determine all possible paths between a number of addresses
1.     var allRoutes:XML =
2.     <routes>
3.         <zip n="3014CD" t="0">
4.             <zip n="1011AB" t="50"/>
5.             <zip n="9714AM" t="55"/>
6.             <zip n="2727" t="78"/>
7.         </zip>
8.             <zip n="1011AB" t="0">
9.             <zip n="3014CD" t="50"/>
10.             <zip n="9714AM" t="20"/>
11.             <zip n="2727" t="10"/>
12.         </zip>
13.             <zip n="9714AM" t="0">
14.             <zip n="3014CD" t="55"/>
15.             <zip n="1011AB" t="20"/>
16.             <zip n="2727" t="25"/>
17.         </zip>
18.         <zip n="2727" t="0">
19.             <zip n="3014CD" t="78"/>
20.             <zip n="1011AB" t="10"/>
21.             <zip n="9714AM" t="25"/>
22.         </zip>
23.     </routes>;
24.     var hash:Array = [];
25.     function shortestCircut(routes:XML, startPoint:String, endPoint:String):int
26.     {
27.         if (!routes.*.length()) return int.MAX_VALUE - int(routes.@t);
28.         trace(startPoint, " => ", endPoint);
29.         trace("---------------------------");
30.         trace(routes.toXMLString());
31.         trace("---------------------------");
32.         var startZip:XML = routes.*.(@n == startPoint)[0];
33.         var endZip:XML = routes.*.(@n == endPoint)[0];
34.         var pTime:int = routes.hasOwnProperty("@t") ? int(routes.@t) : 0;
35.         var time:int = int(startZip.*.(@n == endPoint).@t) + pTime;
36.         if (time == pTime) return int.MAX_VALUE - pTime;
37.         trace("pTime:", pTime, "time:", time);
38.         var available:XMLList = startZip.*.(int(@t) < time);
39.         var availableZips:Array = [];
40.         available.(availableZips.push(String(@n)));
41.         var totalAvailables:XMLList =
42.         routes.*.((valueOf() !== startZip &&
43.         availableZips.indexOf(String(@n)) > -1) ?
44.         true : !hash.push(String(@n)));
45.         var unavailable:XMLList = routes..*.(int(@t) >= time);
46.         while (unavailable.length())
47.         {
48.             delete unavailable[0];
49.         }
50.         delete routes.*.(@n == endPoint)[0];
51.         if (!routes.*.length()) time;
52.         var lookUp:XML;
53.         var addedTime:int;
54.         for each (var n:String in availableZips)
55.         {
56.             lookUp = totalAvailables.(@n == n)[0];
57.             addedTime = pTime + int(available.(@n == n)[0].@t);
58.             unavailable =
59.                 routes.*.(@n == n && (@t = int(@t) +
60.                 addedTime)).*.(int(@t) + addedTime >= time);
61.             while (unavailable.length())
62.             {
63.                 delete unavailable[0];
64.             }
65.         }
66.         unavailable = routes.*.(hasSimpleContent());
67.         while (unavailable.length())
68.         {
69.             delete unavailable[0];
70.         }
71.         totalAvailables = routes.*.(valueOf() !== startZip);
72.         delete routes.*.(valueOf() === startZip)[0];
73.         if (!routes.*.length()) time;
74.         while (routes.*.length())
75.         {
76.             routes.@t = routes.*[0].@t;
77.             addedTime = shortestCircut(routes.copy(), routes.*[0].@n, endPoint);
78.             trace(time, "- adding -", routes.*[0].@t, "- next approach -", addedTime);
79.             if (addedTime < time) time = addedTime;
80.             delete routes.*[0];
81.         }
82.         trace("<--------------------------->");
83.         return time;
84.     }
85.     trace(shortestCircut(allRoutes.copy(), "2727", "3014CD"));