Has to be at least O(V^2) on a serial processor at any rate, because there are that many routes. WFL On 9/12/14, Charles Greathouse <charles.greathouse@case.edu> wrote:
Sure, just like you could make a table of all shortest paths and then spend only constant time for each. What's the best batch complexity for finding all shortest paths?
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Sep 12, 2014 at 11:55 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Setting up only needs to be done once (in principle); then you can find as many shortest-paths as you like in constant time each. WFL
On 9/12/14, Charles Greathouse <charles.greathouse@case.edu> wrote:
Sounds like O(E + V) to me, unless you assume that the input is in the form of a wax-and-string model.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Sep 12, 2014 at 10:51 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
The SWASC (Sealing-Wax and String Computer) had a walk on and trip up part when I discussed finding shortest paths between towns on a road-map in my Algorithms course.
Set-up: (1) Cut the string into segments representing town-to-town distances; (2) Join the ends together with wax blobs representing towns.
Operation: (3) Grasp start and finish towns in left and right hand resp. (4) Pull.
Output: (5) The straight line of string gives the shortest route. Unless you pulled too hard. Or your arms were too short.
Performance: constant time: knocking Dijkstra's algorithm into a cocked hat. Along with itself when it overheats.
WFL
* Henry Baker <hbaker1@pipeline.com> [Sep 12. 2014 08:17]:
[...]
I'd be interested in any other proposals for "steampunk" mathematics.
[...]
Does the "quaternion machine" described on pp.232-234 in the "Book of numbers" by Conway/Guy qualify?
Best, jj
P.S.: I recall building such a TEA laser. Turned out to be quite fiddly (very sensitive to the exact geometry).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun