OUTPUT.txt

We found a way that includes 23 stations and requires 2 transfers
Route plan: Akademmistechko -> Zhytomyrska -> Sviatoshyn -> Nyvky -> Shuliavska -> Politekhnichnyi Instytut -> Vokzalna -> Universytet -> Teatralna -> Khreshchatyk -> Maidan Nezalezhnosti -> Ploshcha Lva Tolstoho -> Palats Sportu -> Klovska -> Pecherska -> Druzhby Narodiv -> Vydubychi -> Slavutych -> Osokorky -> Pozniaky -> Kharkivska -> Vyrlytsia -> Boryspilska
Consider make a transfer from Khreshchatyk to Maidan Nezalezhnosti
Consider make a transfer from Ploshcha Lva Tolstoho to Palats Sportu

We found a way that includes 21 stations and requires 1 transfers
Route plan: Akademmistechko -> Zhytomyrska -> Sviatoshyn -> Nyvky -> Shuliavska -> Politekhnichnyi Instytut -> Vokzalna -> Universytet -> Teatralna -> Zoloti Vorota -> Palats Sportu -> Klovska -> Pecherska -> Druzhby Narodiv -> Vydubychi -> Slavutych -> Osokorky -> Pozniaky -> Kharkivska -> Vyrlytsia -> Boryspilska
Consider make a transfer from Teatralna to Zoloti Vorota

sp.py

#!/usr/bin/env python

import sys, re

class ptroute(object):
	lines = dict()
	graph = dict()
	idtostation = dict()
	stationtoid = dict()
	stationsinlines = dict()

	def __init__(self, db):
		routedbf = open(db, "r")
		currentline = None
		sti = 0

		for l in routedbf.readlines():
			if l[0] == "#" or l[0] == " ":
				continue

			if l[0] == "L":
				currentline = l[2:].strip()
				self.lines[currentline] = list()
				stli = 0
				continue

			if l[0] == "S":
				if currentline == None:
					raise Exception("S without L, wrong file format")

				i = 0
				lsp = 0
				stations = l[2:].strip() + "\n"

				while i < len(stations):
					if stations[i] == "<" or stations[i] == ">" or stations[i] == "\n":

						station = dict(
							id = sti,
							name = stations[lsp:i].strip(),
							canarrive = False,
							candepart = False,
							cantransfer = None,
						)

						if stations[i] == "<":
							station["canarrive"] = True

							if stations[i + 1] == ">":
								station["candepart"] = True
								i = i + 1

						elif stations[i] == ">":
							station["candepart"] = True

						tp = station["name"].find("^")

						if tp != -1:
							station["cantransfer"] = station["name"][tp + 1:].strip()
							station["name"]  = station["name"][0:tp].strip()

						self.lines[currentline].append(station)  

						lsp = i + 1
						sti = sti + 1
						stli = stli + 1

					i = i + 1

		for i in self.lines:
			j = 0
			while j < len(self.lines[i]):
				self.idtostation[self.lines[i][j]["id"]] = self.lines[i][j]
				self.stationtoid[self.lines[i][j]["name"]] = self.lines[i][j]["id"]
				j = j + 1


		for i in self.lines:
			j = 0
			while j < len(self.lines[i]):
			
				if not self.lines[i][j]["id"] in self.stationsinlines:
					self.stationsinlines[self.lines[i][j]["id"]] = list()

				self.stationsinlines[self.lines[i][j]["id"]].append(i)
				self.graph[self.lines[i][j]["id"]] = dict()

				j += 1

			j = 0
			while j < len(self.lines[i]):
				if self.lines[i][j]["candepart"] == True:
					self.graph[self.lines[i][j]["id"]][self.lines[i][j + 1]["id"]] = 1

				if self.lines[i][j]["canarrive"] == True:
					self.graph[self.lines[i][j + 1]["id"]][self.lines[i][j]["id"]] = 1

				if self.lines[i][j]["cantransfer"] != None:
					self.graph[self.lines[i][j]["id"]][self.stationtoid[self.lines[i][j]["cantransfer"]]] = 5

				j += 1		

	# Recursive all path solution
	def searchloop(self, start, end, path=None, maxdepth=30):

		if path == None:
			path = list()

		if maxdepth == 0:
			return []

		path = path + [start]

		if start == end:
			return [path]

		if not self.graph.has_key(start):
			return []

		paths = []

		for node in self.graph[start]:
			if node not in path:
				newpaths = self.searchloop(node, end, path, maxdepth= maxdepth - 1)
				for newpath in newpaths:
					paths.append(newpath)
		return paths

	# Dijkstra shortest path
	# http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/
	def dijkstrashp(self, start, end):
		import heapq

		def flatten(L):
			while len(L) > 0:
				yield L[0]
				L = L[1]

		q = [(0, start, ())]
		visited = set()  

		while True:
			(cost, v1, path) = heapq.heappop(q)
			if v1 not in visited:
				visited.add(v1)
				if v1 == end:
					return list(flatten(path))[::-1] + [v1]

				path = (v1, path)
				for (v2, cost2) in self.graph[v1].iteritems():
					if v2 not in visited:
						heapq.heappush(q, (cost + cost2, v2, path))

	# Bellman-Ford shortest path
	def bellmanfordshp(self, start, end):
		d = dict()
		p = dict()

		for node in self.graph:
			d[node] = float('Inf')
			p[node] = None

		d[start] = 0 

		for i in range(len(self.graph) - 1):
			for u in self.graph:

				if u == end: 
					break

				for v in self.graph[u]:

					if d[v] > d[u] + self.graph[u][v]:
						d[v]  = d[u] + self.graph[u][v]
						p[v] = u
		path = []

		while True:
			path.append(end)
			if end == start: break
			end = p[end]

		path.reverse()

		return path

	# A-star shortest path
	def astarshp(self, start, target):
		import heapq

		graph = self.graph.copy()

		closedset = []
		openset = [(0, start)]
		came_from = dict()
		g_score = dict()
		g_score[start] = 0 

		def reconstruct_path(came_from, current_node):
			if current_node in came_from:
				p = reconstruct_path(came_from, came_from[current_node])

				if type(p) is int: return [p, current_node]
				else: 
					p.append(current_node)
					return p
			else:
				return current_node

		while len(openset):
			(f_score,current) = heapq.heappop(openset)

			if current == target:
				return reconstruct_path(came_from, target)

			closedset.append(current)

			for neighbor in graph[current]:
				if neighbor in closedset:
					continue

				tentative_g_score = g_score[current] + graph[current][neighbor]

				if neighbor not in g_score:
					g_score[neighbor] = float("Inf")

				if neighbor not in g_score:
					g_score[neighbor] = float("Inf")

				if (graph[current][neighbor], neighbor) not in openset or tentative_g_score <= g_score[neighbor]:
					came_from[neighbor] = current
					g_score[neighbor] = tentative_g_score

					if target not in graph[neighbor]:
						graph[neighbor][target] = float("Inf")

					f_score = g_score[neighbor] + graph[neighbor][target]

					if (f_score, neighbor) not in openset:
						heapq.heappush(openset, (f_score, neighbor))


	def find(self, start, end, maxdepth=1000, alg="loop"):
		try: start = self.stationtoid[start]
		except KeyError: return None

		try: end = self.stationtoid[end]
		except KeyError: return None

		result = list()
		pathresults = list()

		reverse = None

		if alg in ("dijkstra", "bellmanford", "astar"):
			if start > end:
				reverse = start
				start = end
				end = reverse

		if alg == "loop":
			pathresults = self.searchloop(start, end, maxdepth=maxdepth)
		elif alg == "dijkstra":
			pathresults = [self.dijkstrashp(start, end)]
		elif alg == "bellmanford":
			pathresults = [self.bellmanfordshp(start, end)]
		elif alg == "astar":
			pathresults = [self.astarshp(start, end)]

		if not reverse == None:
			pathresults.reverse()


		for path in pathresults:
			pathlines = set()
			pathnames = list()
			transfers = list()
			transfersnames = list()

			i = 0
			while i < len(path):
				pathlines.add(self.stationsinlines[path[i]][0])
				pathnames.append(self.idtostation[path[i]]["name"])

				if self.idtostation[path[i]]["cantransfer"] != None and i < len(path) - 1:

					tid = self.stationtoid[self.idtostation[path[i]]["cantransfer"]]
					if path[i + 1] == tid:
						transfers.append((path[i],path[i + 1]))
						transfersnames.append((self.idtostation[path[i]]["name"], self.idtostation[path[i + 1]]["name"]))

				i = i + 1

			result.append({
				"transferscnt": len(pathlines) - 1,
				"transfersid": transfers,
				"transfersname": transfersnames, 
				"stationscnt": len(path),
				"stationsid": path,
				"stationsname": pathnames
			})

		return result

# TEST DATA AND DATABASE

kiyvsubway = ptroute(db="subway.txt")

for possiblepath in kiyvsubway.find("Minska", "Vyrlytsia", alg="bellmanford"):
	print "We found a way that includes %d stations and requires %d transfers" % (possiblepath["stationscnt"], possiblepath["transferscnt"])
	print "Route plan:", " -> ".join(possiblepath["stationsname"])
	for transfer in possiblepath["transfersname"]:
		print "Consider make a transfer from %s to %s" % transfer
	print "\n"

subway.txt

# Kiev Subway
# 22.11.2012
# subway optimal routes searching example

# Red Line 
L: Sviatoshynsko-Brovarska Line
S: Akademmistechko <> Zhytomyrska <> Sviatoshyn <> Nyvky <> Shuliavska <> Politekhnichnyi Instytut <> Vokzalna <> Universytet <> Teatralna ^ Zoloti Vorota <> Khreshchatyk ^ Maidan Nezalezhnosti <> Arsenalna <> Dnipro <> Hidropark <> Livoberezhna <> Darnytsia <> Chernihivska <> Lisova

# Blue Line 
L: Kurenivsko-Chervonoarmiyska Line
S: Heroiv Dnipra <> Minska <> Obolon <> Petrivka <> Tarasa Shevchenka <> Kontraktova Ploshcha <> Poshtova Ploshcha <> Maidan Nezalezhnosti ^ Khreshchatyk <> Ploshcha Lva Tolstoho ^ Palats Sportu <> Olimpiiska <> Palats "Ukrayina" <> Lybidska <> Demiivska <> Holosiivska <> Vasylkivska <> Vystavkovyi Tsentr

# Green Line
L: Syretsko-Pecherska Line
S: Syrets <> Dorohozhychi <> Lukianivska <> Zoloti Vorota ^ Teatralna <> Palats Sportu ^ Ploshcha Lva Tolstoho <> Klovska <> Pecherska <> Druzhby Narodiv <> Vydubychi <> Slavutych <> Osokorky <> Pozniaky <> Kharkivska <> Vyrlytsia <> Boryspilska <> Chervony Khutir