problem creating optimization algorithm

[mariokartlegendd]

The nature of my problem is to design a hypothetical transit system for a city. The input file is very specific, in that it only lists one-way legs that are not reverse routes. It is of the form <cost> <origin> <destination>, for example:

4000     downtown     beach
8000     beach        stadium
2000     stadium      valley
1100     valley       downtown
900      downtown     stadium
4000     beach        valley
3000     stadium      beach

The goal is to find the cheapest CONNECTED path - implying each location has a route containing it as both a origin and destination (to different places), so the solution in this example would look like:

the route comprised of the bottom 4 entries of the input file (lesser cost than path of the top 4 entries of the input file )

valley -> downtown
   ^          |
   |          v
beach <-  stadium

I am very new to greedy algorithms, but I need to find a decently scalable solution as I will be blind to the input file which may contain, let's say , 4 to 12 different locations.

What kind of algorithm can I use for this? I understand the nature behind minimum spanning trees, but most of those don't take "to" and "from" direction into account. I am thoroughly confused about this, and I don't see any simple algorithmic solution to use...

[helios]

A*?
http://en.wikipedia.org/wiki/A*

[csiz]

or dijkstra as a* is good where you can aproximate the cost (like a grid... like in those rts games where a unit has to find a way to where you click and the shortest would be targetx-startx+targety-starty).

search dijkstra on google it works for any graph

[mariokartlegendd]

so helios and others, if i use a* , reading about it i think i understand it somewhat, but i am confused how i specify nodes...

do i think of it like beach is one point, downtown another, and the distance is simply the distance...

it sounds fine, but i ask b/c how will i know how to discriminate between stadium -> beach (3000) and beach -> stadium (8000) ?

but my main question is, how do i use a* when i have an unknown goal state?? i dont know what my goal solution is like since i am blind to the input file. i am going to continue reading about this but i wanted to ask these important questions. thx