Algoritmo para calcular a existência de caminhos em cruzamento.

caminho_transito.py

grafo = {
	'0': ['6'],
	'1': ['2', '6'],
	'2': ['1', '3', '7'],
	'3': ['2'],
	'4': ['3', '5'],
	'5': ['4', '10'],
	'6': ['0', '1', '7'],
	'7': ['6', '12', '13'],
	'8': ['3', '7', '9', '13'],
	'9': ['4', '8', '10', '14'],
	'10': ['5', '9'],
	'11': ['6', '12', '16'],
	'12': ['7', '11', '13', '17'],
	'13': ['8', '18'],
	'14': ['9', '15', '19'],
	'15': ['10', '20'],
	'16': ['11', '17', '21'],
	'17': ['12', '16', '18', '22'],
	'18': ['13', '19'],
	'19': ['14', '18', '20'],
	'20': ['15', '19', '25', '50'],
	'21': ['16', '22'],
	'22': ['17', '21', '23'],
	'23': ['18', '22', '24'],
	'24': ['19', '23', '25'],
	'25': ['24', '20'],
	'50': []
}

prbs = {
	'2': {'1': ['3'], '3': ['1']},
	'4': {'9': ['3']},
	'8': {'3': ['7'], '7': ['3'], '9': ['13'], '13': ['9']},
	'9': {'4': ['8', '10'], '8': ['4', '14'], '10': ['4'], '14': ['8']},
	'10': {'15': ['9']},
	'12': {'7': ['11', '17'], '11': ['7'], '17': ['7']},
	'14': {'19': ['15']},
	'15': {'14': ['10']},
	'17': {'12': ['22'], '16': ['22'], '22': ['16']},
	'19': {'24': ['14']},
	'20': {'19': ['25', '50'], '15': ['50'], '25': ['19']}
}

def e_proibido(proibicoes, atual, origem, destino):
	if origem is None:
		return True # Edge case para o início, que não possui origem
	elif atual in proibicoes:
		if origem in proibicoes[atual]:
			if destino in proibicoes[atual][origem]:
				return True
	return False

def encontra_caminho(grafo, atual, fim, caminho=None, anterior=None):
	if caminho is None: caminho = []
	caminho += [atual]
	if atual == fim:
		return caminho
	if atual not in grafo:
		return None
	if fim not in grafo:
		return None
	for prox in grafo[atual]:
		if (prox not in caminho) and not (e_proibido(prbs, atual, anterior, prox)):
			novo_caminho = encontra_caminho(grafo, prox, fim, caminho, atual)
			if novo_caminho: return novo_caminho
			else: caminho.remove(prox)
	return None

def encontra_caminho_sem_proibicoes(grafo, atual, fim, caminho=None, anterior=None):
	if caminho is None: caminho = []
	caminho += [atual]
	if atual == fim:
		return caminho
	if atual not in grafo:
		return None
	if fim not in grafo:
		return None
	for prox in grafo[atual]:
		if (prox not in caminho):
			novo_caminho = encontra_caminho_sem_proibicoes(grafo, prox, fim, caminho, atual)
			if novo_caminho: return novo_caminho
			else: caminho.remove(prox)
	return None

print('Calcula caminho...')
a = encontra_caminho(grafo, '0', '50')
print('Caminho: {0}'.format(a))

print('Calcula caminho (sem proibições de curva) ...')
a = encontra_caminho_sem_proibicoes(grafo, '0', '50')
print('Caminho (sem proibições): {0}'.format(a))

regras_transito.jpg

resultado.txt

Python 3.5.1 (default, Dec 2015, 13:05:11)
[GCC 4.8.2] on linux

Calcula caminho...
Caminho: None
Calcula caminho (sem proibições de curva) ...
Caminho (sem proibições): ['0', '6', '1', '2', '7', '12', '11', '16', '17', '18', '13', '8', '9', '14', '15', '20', '50']

Como solução, a imagem acima foi mapeada como um grafo dirigido em Python, onde cada cruzamento é o vértice de um grafo dirigido armazenado em um dicionário de vértices e cada direção deste vértice para o próximo é um item de uma lista deste item do dicionário. Para considerar as permissões de curva à partir de um vértice, é necessário estabelecer qual o vértice anterior do caminho, e para isso é necessário criar um outro dicionário onde são armazenadas as proibições de direção de um vértice a outro, considerando a origem.

Fazendo-se uma análise do resultado com e sem as proibições de curva e somente pelas conexões com os próximos vértices, podemos notar que o grafo com menor caminho encontrado pelos algoritmos [1] e [2] são consonantes até o vértice 12, com uma dissonância de decisão à partir dele, para o vértice 11, onde existe uma proibição de curva, assim com em outras opções exploradas pelo algoritmo [1].

Desta forma, considerando-se as proibições de curvas, não existe caminho que leve do ponto 0 ao ponto 50. Desconsiderando as proibições, o caminho é o seguinte: ['0', '6', '1', '2', '7', '12', '11', '16', '17', '18', '13', '8', '9', '14', '15', '20', '50']

Update: Contradizendo a resposta, existe uma opção de caminho que não é contemplada pelo código pelo fato de o algoritmo de Dijkstra, no qual a busca foi baseada, desconsiderar loopings e em nosso caso em específico, existem regras adicionais que podem fazer uso de loops e mesmo assim não entrar em recursão infinita.

Desta forma, o algoritmo é incompleto e existe uma solução, e exige passar por um caminho já visitado anteriormente: 6 -> 7 -> 8 -> 13 -> 18 -> 19 -> 14 -> 9 -> 4 -> 5 -> 10 -> 9 -> 14 -> 15 -> 20 -> 25 -> 20 -> 50.

[1] : encontra_caminho()
[2] : encontra_caminho_sem_proibicoes()