Найти быстрый путь - PullRequest
Новая
       13

Найти быстрый путь

0 голосов
/ 24 апреля 2020

У меня есть список поездов с расписанием прибытия на различные станции.

Мне нужно найти самый быстрый путь между двумя железнодорожными станциями, если это возможно.

Для этого я даже разрешено менять поезд один раз в течение всего пути.
Однако . Если я меняю поезд, я должен также добавить время ожидания при посадке в другой поезд.
Ниже приведен псевдокод, который у меня есть. написано, но я сталкиваюсь с проблемами при его заполнении. Особенно во время смены поезда и учета времени ожидания. Может ли кто-нибудь помочь мне с этим и исправить мой псевдокод. 

function findFastestPath(source_station,dest_staion,waiting_time_at_current_station,travel_time_in_previous_train):
    for each train_schedule in TrainList:
        while train_schedule is not over:
            if source_station equals train_schedule[station]
            Then
                if dest_staion in train_schedule
                Then
                    if dest_staion[departure_time] > source_station[departure_time]
                    Then
                        duration = dest_staion[departure_time] - source_station[departure_time] + waiting_time_at_current_station + travel_time_in_previous_train
                        if mintime > duration
                        Then
                            mintime = duration
                else:
                   travel_time_in_previous_train = next_station_to_source_station[departure_time]-source_station[departure_time]
                   waiting_time_at_current_station = next_train_departure_time - next_station_to_source_station[departure_time]
                   call findFastestPath(next_station_to_source_station, dest_staion, waiting_time_at_current_station, travel_time_in_previous_train)            
        return mintime
end function

for each source_station in Travel_Time_Matrix:
    for each dest_staion in Travel_Time_Matrix:
        call findFastestPath(source_station,dest_staion,0,0)

1 Ответ

0 голосов
/ 26 апреля 2020 
FindFastestPathInSameTrain(src,dest):
    For x in range(Len(TrainList)):                                    //TrainList is a two dimentional array which has each train schedule in each row
        IF src and dest in TrainList[x]:                               
            IF dest(time) > src(time):                                 // Here we are checking if destination station is not before source station in train
                duration = src->departuretTime - dest->departuretTime  // calculating duration
                IF min > duration:                                     // min value will be updated if as we find fastest fast in other trains
                    min = duration
        else:
            NewTrainList.add(TrainList[x])                             // if line 2 is not satisfied we will add that train in NewTrainList which is 2d array
    return min                                                 // by default  min value will be 1000, and it will be returned in case of no direct train

FindFastestPathInSecondTrain(src,dest):                                // now we will work on trains which dont has both source and destination station
   For x in range(Len(NewTrainList)):                                  // we will iterate NewTrainList
       IF src in NewTrainList[x]:                                      // if we find our Source station in NewTrainList
           For n in range(NewTrainList[x].index(src)+1,len(NewTrainList[x])): // we will iterate that trains remaining station as src in a new extended function
               FindFastestPathInSecondTrainExtension(NewTrainList[n],dest,src->departuretTime) 

// this comment is for line 16 : Just as our FindFastestPathInSameTrain(), but here we will send origin departuretTime so as to capture time spent in prev train + waiting time at connecting station.

FindFastestPathInSecondTrainExtension(newsrc,dest,src->departuretTime): // This function will work similar to FindFastestPathInSameTrain()
    For x in range(Len(NewTrainList)):
        IF newsrc and dest in NewTrainList[x]:
            IF dest->departuretTime > newsrc->departuretTime
                secondDuration = (dest->departuretTime - newsrc->departuretTime) + (newsrc->departuretTime - src->departuretTime)
                IF min > secondDuration
                   min = secondDuration
    return min

For each source_station in Travel_Time_Matrix:                         // Iterating all the source_station
    For each dest_staion in Travel_Time_Matrix:                        // Iterating all the dest_station
        T1 = FindFastestPathInSameTrain(source_station,dest_station)   
        T2 = FindFastestPathInSecondTrain(source_station,dest_station)
        IF T1 < T2
           write T1
        ELSE:
           write T2
...