Banfa 9,065
Expert Mod 8TB
Attached is a map of the Scriptsville Metro.
Produce an algorithm that given a starting station and a finishing station will produce 2 routes:
1. The route that passes through the fewest stations
2. The route that requires the fewest number of transfers but otherwise passes through the fewest number of stations
Given that it takes 5 minutes to travel between each station and transfering also takes 5 minutes for each route give the following output
1. Starting Station
2. Finishing Station
3. Each station at which you need to transfer
4. Total number of stations visited inclusive of the starting and finish stations
5. Total number of transfers made
6. Total time for the journey
Use any language or package you like to solve this problem (VB, pseudo code, C/C++, SQL, Python etc), +kudos to anyone producing a Prologue solution.
Yoursolution should
1. Indicate the data structures used to encode the map for the computer
2. Provide the algorithm to operate on this data to produce the required results.
Further Questions
For any possible configuration of a multilined metro system is it guaranteed that one of the 2 routes produced by your algorithm will be the quickest for all possible journeys?
For the metro system in the map is it guaranteed that one of the 2 routes produced by your algorithm will be the quickest for all possible journeys?
5 2986
Nah, that's an MCNF (Minimal Cost Network Flow) problem (cost on nodes and
edges). Does a book reference count?
kind regards,
Jos
Banfa 9,065
Expert Mod 8TB
Nah, that's an MCNF (Minimal Cost Network Flow) problem (cost on nodes and
edges). Does a book reference count?
With the utmost respect Jos, if it isn't a challenge for you then there is no need to attempt it :p You could of course set your own :D
With the utmost respect Jos, if it isn't a challenge for you then there is no need to attempt it :p You could of course set your own :D
I'd like to propose the following silly problem as a contestant: http://www.thescripts.com/forum/thread717662.html
No arrays allowed (and no more advanced containers either ;-) The resulting
program will be a highly convoluted, obfuscated thingy, no doubt about about it.
I'm no game when it comes to those stinky operations research like problems
such as your proposed MCNF thingy; I even don't dare to tell my old mom that I
deal with those monsters on a daily basis; I feel so ashamed; so .. so .. smeared ;-)
kind regards,
Jos *sob*
For any possible configuration of a multilined metro system is it guaranteed that one of the 2 routes produced by your algorithm will be the quickest for all possible journeys?
With the configuration given, I think it is the case. However the answer is no in general.
For example take the configuration
1-2-3-4-5-6-7-8-9-10-11-12
Assume there is a train that goes all the way from 1-12
Also assume there are trains
1-4,
4-7,
7-10
10-12
1-3-6
6-9-12
The route with the least number of stations is
1,4,7,10.12 (3 transfers)
However, this takes 7X5 = 35 mins
The route with the least number of transfers is
1,2,3,4,5,6,7,8,9,10,11,12 (0 transfers)
11 X 5 = 55 mins
Fastest route
1,3,6,9,12 (1 transfer)
5X5 = 25 mins.
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Ken |
last post by:
This is a challenge. Perhaps someone can offer suggestions.
I am trying to create a variable, ordernumber, that increases by an
increment of 1 every time the variable is accessed.
For...
|
by: Frank Buss |
last post by:
A new challenge:
http://www.frank-buss.de/marsrescue/index.html
Have fun! Now you can win real prices.
--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
|
by: Richard Jones |
last post by:
The date for the second PyWeek challenge has been set: Sunday 26th March
to Sunday 2nd April (00:00UTC to 00:00UTC).
The PyWeek challenge invites entrants to write a game in one week from...
|
by: richard |
last post by:
The date for the second PyWeek challenge has been set: Sunday 26th March
to Sunday 2nd April (00:00UTC to 00:00UTC).
The PyWeek challenge invites entrants to write a game in one week from...
|
by: smd |
last post by:
Hello and thanks for taking the time to help out. I've been tasked
with finding records from one table that are not in another table, but
do exist in a third. I've written a query that identifies...
|
by: cyberco |
last post by:
I've posted this question in
'microsoft.public.dotnet.framework.compactframework' as well, but
despite the great help I still haven't solved the problem. So before
going the C++ route I would like...
|
by: Thierry |
last post by:
For those interested in <b>programming riddles</b>, I would like to
announce a new programming challenge I'm just launching at
http://software.challenge.googlepages.com
This challenge is in its...
|
by: Glenton |
last post by:
Hi All
Here is a very simple little class for finding a shortest route on a network, following Dijkstra's Algorithm:
#!/usr/bin/env python
#This is meant to solve a maze with Dijkstra's...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |