title: Ð¡ÑÐ°Ð²Ð½Ð¸ÑÐµÐ»ÑÐ½ÑÐ¹ Ð°Ð½Ð°Ð»Ð¸Ð· Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² Ð¿Ð¾Ð¸ÑÐºÐ° Ð¼Ð°ÑÑÑÑÑÐ¾Ð² Ð¿Ð¾ÐµÐ·Ð´Ð¾Ð² Ñ Ð½ÐµÑÐºÐ¾Ð»ÑÐºÐ¸Ð¼Ð¸ Ð·Ð°Ð´Ð°Ð½Ð½ÑÐ¼Ð¸ ÑÐ¾ÑÐºÐ°Ð¼Ð¸
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð±Ð°ÐºÐ°Ð»Ð°Ð²ÑÐ°
titleType: Subtitle
title: Comparative analysis of algorithms for finding train routes with several specified points
Creators: name: ÐÐ¾ÑÐºÐ¾Ð²Ð°, ÐÐ»ÐµÐºÑÐ°Ð½Ð´ÑÐ°
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2024
Subjects: ÐºÑÐ°ÑÑÐ°Ð¹ÑÐ¸Ð¹ Ð¿ÑÑÑ
Ð·Ð°Ð´Ð°ÑÐ° ÐºÐ¾Ð¼Ð¼Ð¸Ð²Ð¾ÑÐ¶ÐµÑÐ°
Ð¼ÐµÑÑÐ¾
Ð¼Ð°ÑÑÑÑÑ Ð´Ð²Ð¸Ð¶ÐµÐ½Ð¸Ñ Ð¿Ð¾ÐµÐ·Ð´Ð¾Ð²
Ð²Ð·Ð²ÐµÑÐµÐ½Ð½ÑÐ¹ Ð³ÑÐ°Ñ
Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼
Ð¼ÐµÑÐ¾Ð´
shortest path
traveling salesmans problem
metro
train route
weighted graph
algorithm
method

description: Ð¢ÐµÐ¼Ð° Ð²ÑÐ¿ÑÑÐºÐ½Ð¾Ð¹ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð¾Ð¹ ÑÐ°Ð±Ð¾ÑÑ: Â«Ð¡ÑÐ°Ð²Ð½Ð¸ÑÐµÐ»ÑÐ½ÑÐµ Ð°Ð½Ð°Ð»Ð¸Ð· Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² Ð¿Ð¾Ð¸ÑÐºÐ° Ð¼Ð°ÑÑÑÑÑÐ¾Ð² Ð¿Ð¾ÐµÐ·Ð´Ð¾Ð² Ñ Ð½ÐµÑÐºÐ¾Ð»ÑÐºÐ¸Ð¼Ð¸ Ð·Ð°Ð´Ð°Ð½Ð½ÑÐ¼Ð¸ ÑÐ¾ÑÐºÐ°Ð¼Ð¸Â». Ð¦ÐµÐ»ÑÑ ÑÐ°Ð±Ð¾ÑÑ ÑÐ²Ð»ÑÐµÑÑÑ Ð¾Ð¿ÑÐµÐ´ÐµÐ»ÐµÐ½Ð¸Ðµ Ð¾Ð¿ÑÐ¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð³Ð¾ (ÑÐ°Ð¼Ð¾Ð³Ð¾ Ð±ÑÑÑÑÐ¾Ð³Ð¾) Ð¼Ð°ÑÑÑÑÑÐ° Ð´Ð²Ð¸Ð¶ÐµÐ½Ð¸Ñ Ð¿Ð¾ÐµÐ·Ð´Ð¾Ð² ÑÐµÑÐµÐ· Ð½ÐµÑÐºÐ¾Ð»ÑÐºÐ¾ Ð·Ð°Ð´Ð°Ð½Ð½ÑÑ ÑÑÐ°Ð½ÑÐ¸Ð¹. ÐÐ»Ñ Ð´Ð¾ÑÑÐ¸Ð¶ÐµÐ½Ð¸Ñ ÑÐµÐ»Ð¸ Ð² Ð¿ÑÐ¾ÑÐµÑÑÐµ ÑÐ°Ð±Ð¾ÑÑ ÑÐµÑÐ°Ð»Ð¸ÑÑ ÑÐ»ÐµÐ´ÑÑÑÐ¸Ðµ Ð·Ð°Ð´Ð°ÑÐ¸: 1) ÐÐ·ÑÑÐ¸ÑÑ Ð¸Ð½ÑÐ¾ÑÐ¼Ð°ÑÐ¸Ñ Ð¾ Ð´Ð²Ð¸Ð¶ÐµÐ½Ð¸Ð¸ Ð¿Ð¾ÐµÐ·Ð´Ð¾Ð²; 2) ÐÐ·ÑÑÐ¸ÑÑ Ð¼ÐµÑÐ¾Ð´Ñ ÑÐ¾ÑÐ¼Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸Ñ Ð¾Ð¿ÑÐ¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð³Ð¾ Ð¿ÑÑÐ¸; 3) Ð ÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°ÑÑ Ð²ÑÐµ ÑÐ°ÑÑÐ¼Ð¾ÑÑÐµÐ½Ð½ÑÐµ Ð¼ÐµÑÐ¾Ð´Ñ Ð½Ð° python; 4) ÐÑÐ¾Ð´ÐµÐ¼Ð¾Ð½ÑÑÑÐ¸ÑÐ¾Ð²Ð°ÑÑ ÑÐ°Ð±Ð¾ÑÐ¾ÑÐ¿Ð¾ÑÐ¾Ð±Ð½Ð¾ÑÑÑ ÑÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ð¸ Ð½Ð° Ð¿ÑÐ¸Ð¼ÐµÑÐµ Ð¼ÐµÑÑÐ¾ Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³Ð°; 5) ÐÑÐ¾Ð²ÐµÑÑÐ¸ ÑÑÐ°Ð²Ð½Ð¸ÑÐµÐ»ÑÐ½ÑÐ¹ Ð°Ð½Ð°Ð»Ð¸Ð· ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ð½ÑÑ Ð¼ÐµÑÐ¾Ð´Ð¾Ð²; 6) ÐÑÐµÐ´Ð»Ð¾Ð¶Ð¸ÑÑ Ð¼Ð¾Ð´Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ñ Ð¼ÐµÑÐ¾Ð´Ð° ÑÐ¾ÑÐ¼Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸Ñ Ð¾Ð¿ÑÐ¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð³Ð¾ Ð¿ÑÑÐ¸; 7) ÐÑÐ¾Ð²ÐµÑÑÐ¸ ÑÑÐ°Ð²Ð½Ð¸ÑÐµÐ»ÑÐ½ÑÐ¹ Ð°Ð½Ð°Ð»Ð¸Ð· Ð¼Ð¾Ð´Ð¸ÑÐ¸ÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð½Ð¾Ð³Ð¾ Ð¼ÐµÑÐ¾Ð´Ð° Ñ ÑÐ°ÑÑÐ¼Ð¾ÑÑÐµÐ½Ð½ÑÐ¼Ð¸. Ð ÑÐµÐ·ÑÐ»ÑÑÐ°ÑÐµ ÑÐ°Ð±Ð¾ÑÑ ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ñ Ð¼ÐµÑÐ¾Ð´Ñ ÑÐ¾ÑÐ¼Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸Ñ Ð¼Ð°ÑÑÑÑÑÐ° ÑÐµÑÐµÐ· Ð½ÐµÑÐºÐ¾Ð»ÑÐºÐ¾ Ð·Ð°Ð´Ð°Ð½Ð½ÑÑ ÑÑÐ°Ð½ÑÐ¸Ð¹ Ð¸ Ð¿ÑÐ¾Ð²ÐµÑÐµÐ½Ð° Ð¸Ñ ÑÐ°Ð±Ð¾ÑÐ¾ÑÐ¿Ð¾ÑÐ¾Ð±Ð½Ð¾ÑÑÑ Ð½Ð° Ð¿ÑÐ¸Ð¼ÐµÑÐµ Ð¼ÐµÑÑÐ¾ Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³Ð°, Ð° ÑÐ°ÐºÐ¶Ðµ ÑÐ´ÐµÐ»Ð°Ð½ Ð²ÑÐ²Ð¾Ð´ Ð¾ Ð½Ð°Ð¸Ð±Ð¾Ð»ÐµÐµ Ð¿Ð¾Ð´ÑÐ¾Ð´ÑÑÐµÐ¼ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ðµ.
description: The subject of the graduate qualification work is Â« Comparative analysis of algorithms for finding train routes with several specified pointsÂ». The purpose of the work is to determine the optimal (fastest) train route through several specified stations. In order to achieve the purpose, the following goals were solved in the course of the research: 1) Examine the information about the movement of trains; 2) Examine the methods of forming the optimal path; 3) Implement all the considered methods in python; 4) Demonstrate the efficiency of the implementation using the example of the St. Petersburg metro; 5) Conduct a comparative analysis of the implemented methods; 6) Propose a modification of the optimal path formation method; 7) Conduct a comparative analysis of the modified method with the considered ones. As a result of the work, methods for forming a route through several specified stations were implemented and their operability was tested on the example of the St. Petersburg metro, and a conclusion was made about the most suitable algorithm.