Itinéraire le plus court

[Malix-Labs]

Tasks

• [x] #22
• [x] #21
• [x] #14

[osbyrne]

est ce qu'on a des infos additionnelles? Si les correcteurs voudront tester a partir de leur dataset, donc quelle sera la forme de leur dataset; si on travaille sur un graph dirige ou non dirige...

[Malix-Labs]

• Comment from @osbyrne :

  est ce qu'on a des infos additionnelles? ⋯

  A ce que je sais, on devra implémenter

  • Dijkstra
  • Kruskal

  ⋯ Si les correcteurs voudront tester a partir de leur dataset, donc quelle sera la forme de leur dataset ⋯

  On a notre propre dataset (RATP API)

  ⋯ si on travaille sur un graph dirige ou non dirige...

  A voir à partir du dataset ci-dessus

[Malix-Labs]

Algorithm

Dijkstra's Algorithm is the preferable algorithm

Important Context

Since we are dealing solely with the metro network, the complexity is greatly reduced compared to the full multi-modal system. This opens up simpler and potentially faster algorithm options.

Consideration

• Metro Networks are Typically Static: Unlike road networks with fluctuating traffic, metro schedules are relatively fixed. Dijkstra excels in static networks with non-negative edge weights (time or distance).
• Transfers Dominate Travel Time: In metro systems, the time spent waiting for transfers often outweighs the actual travel time between stations. Dijkstra, with appropriate edge weights representing transfer times, can accurately model this.
• Simplicity: Dijkstra is easier to implement and debug than A*, especially when development velocity might be prioritized.
• Sufficient Performance: Metro networks are much smaller than full road networks. Dijkstra's performance is likely adequate for providing quick results in a metro-only app.

References

• Dominik Kirchler. Efficient routing on multi-modal transportation networks. Data Structures and Algorithms [cs.DS]. Ecole Polytechnique X, 2013. English. ffNNT : ff. ffpastel-00877450 (specific example from page 35)