1 Востаннє редагувалося DimONN (12.06.2018 15:20:17)

Тема: Задача про існування маршруту і вибір оптимального

Доброго дня!

Є задача визначити чи існує маршрут між містами. І друга частина - якщо існує декілька. то вибрати оптимальний.

Дойшов тільки ось до чого:

# Пошук маршруту


def base_of_ways(oneway = []):
    global n,base,towns
    n = int(input('Введіть кількість маршрутів '))
    base = {}
    for i in range (0, n):
        t = str(input('Введіть дані маршруту №{} через кому у вигляді: Номер автобусу, Місто відправлення, Місто прибуття, Вартість : '.format(i+1))).split(',')
        oneway.append(t)
        base[int(oneway[i][0])] = [oneway[i][1],oneway[i][2],int(oneway[i][3])]
    return base

def way_check(T=False,TH=False,initial='',final='',route=[],routes={},Cost=0):
    towns = list(str(input('Введіть Ваш маршрут у вигляді: <з якого міста>,<в яке місто>: ')).split(','))
    initial = towns[0]
    final = towns[1]
    for i in base:
        if (base[i][0] == towns[0] or base[i][0] == initial) and base[i][1] == final:
            T = True
            Cost+=base[i][2] 
        elif base[i][0] == towns[0] and base[i][1] != towns[1]:
            towns[0] = base[i][1]
            Cost+=base[i][2]
    if T:
        print('Можна дістатись із міста {} в місто {}. Вартість {}.'.format(initial,final,Cost))
    else:
        print('Не можна дістатись із міста {} в місто {}.'.format(initial,final))
    return T

base_of_ways()
print(base)
way_check()

Розумію, що має бути якийсь рекурсивний алгоритм і необхідно визначити всі можливі шляхи в вигляді списків. Але що робити далі і чи обов язкова рекурсія?

Буду вдячний за пораду!

2

Re: Задача про існування маршруту і вибір оптимального

графи

3 Востаннє редагувалося koala (12.06.2018 16:39:55)

Re: Задача про існування маршруту і вибір оптимального

https://uk.wikipedia.org/wiki/Перевірка … сті_графів
UPD: https://uk.wikipedia.org/wiki/Пошук_шляху (ви не написали, що граф зважений)

4

Re: Задача про існування маршруту і вибір оптимального

Нормальний хід ). Дали на екзамен фундаментальну задачу ))), щоб я її за 45 хвилин розв язав ). Типу молодий Ейлер.

Правда, наприкінці зауважили, що пересадка буде тільки одна )), максимум дві ).

Як треба змінити код, щоби враховувало одну пересадку.

На вході, наприклад:

1,A,B,100
2,B,C,75
3,A,D,175
4,B,D,50

Треба знайти

A,D