Trouver le temps le plus court pour passer d'un arrêt à un autre arrêt dans un système de train avec de nombreuses lignes de train avec des stations de connexion

Question

Alors je pensais après avoir discuté avec mon ami l'autre jour, comment utiliser quelque chose comme la recherche en profondeur ou en profondeur pour trouver le temps le plus rapide pour aller d'une station à une autre station s'il existe un certain nombre de lignes de train différentes dans un système de métro. Ils peuvent se croiser, peut-être plusieurs fois.

La ligne de train dans ce cas signifie un train qui passe d'une station de départ à une station de fin, avec de nombreux arrêts de station en cours de route, où certains arrêts de la station peuvent donner la possibilité que le pilote échange sur une autre "ligne" qui a également son démarrage et la station d'arrêt. Un exemple simple est un système de métro à deux lignes comme tel:

o : station   - : track

                     Line 2 
                     START
                       |
                       o
                       |
Line 1 START o -- o -- o -- o -- o -- o END 
                       |
                      END

J'habite à Taipei, Taiwan, vous pouvez donc référencer la carte du train MRT là-bas pour référence, mais cela peut sembler assez compliqué. Je cherchais des conseils pour un début plus simple et des moyens de trouver une solution à un problème plus petit en premier, mais le système MRT est mon ami et moi l'objectif cible.

Ce que j'ai jusqu'à présent

• Ayez un tableau qui contient chaque nom d'arrêt ainsi que le temps nécessaire à l'arrêt précédent pour atteindre cet arrêt représente une seule ligne de train, chaque connexion à une autre ligne de train étant un tableau imbriqué à cet article.
• Découvrez comment dire à l'algorithme de regarder à travers chaque itinéraire pour trouver l'arrêt de destination, en ajoutant le temps pris en cours de route en comparant pour trouver les temps les plus courts.

Choses à considérer

• Le temps entre chaque station nous est connue. Mais aux fins de cette question, supposons simplement ses 5 minutes entre chaque station.
• Une ligne de train a un arrêt de départ et un arrêt de fin, mais sur le chemin, il peut s'arrêter sur un arrêt qui se connecte à toute autre ligne de train.
• Toute connexion à une autre ligne de train peut se connecter à une autre ligne - mais l'accès à cette troisième ligne peut être atteint en prenant un autre itinéraire plus compliqué en changeant les lignes de train. Cela signifie que si j'essaye toutes les possibilités, cela peut prendre des itinéraires en boucle et tester pour toujours.
  • Il est possible de prendre un transfert d'une ligne à une autre, et d'aller à gauche ou à droite sur la nouvelle ligne, c'est-à-dire que les trains ne sont pas à sens unique.

Alors, comment est-il possible de

Évitez notre algorithme de fabrication de boucles, par exemple:

Si la ligne 1 se connecte à la ligne 2 sur son troisième arrêt, et cela se connecte à une troisième ligne, puis revenez à la ligne 1 plus tard sur la ligne de la ligne 3. Ensuite, si nous devions trouver le moyen le plus court à passer d'un arrêt dans la ligne 1 À un autre arrêt à la ligne 1, l'algorithme peut tester de la ligne 1 à la ligne 2 en prenant la connexion puis à la ligne 3 à la ligne 1 et en arrière.

Et aussi, comment pouvons-nous décider où faire les virages, et quelle est une meilleure façon de représenter ce problème et de trouver le plus court temps?