Қазақстан республикасының білім және ғылым министірлігі

Графтағы ең қысқа маршрутты анықтайтын өте қарапайым әрі тиімді алгоритм бар.

Оны бұрыннан белгілі бас қатырғыш жұмбақ есеп мысалында қарастырайық. Екі адамда вино құйылған 8 литрлік бір құмыра және 5 литрлік, 3 литрлік екі бос құмыра бар. Виноны құмыралар не толық, не бос болатындай құйып, екі адам барлық виноны тең бөлісуі керек.

Алдымен екі мүмкіндікті қарастырамыз: 8 литрлік құмырадан вино 5 литрлік және 3 литрлік құмыраларға құйылады. Бұл мүмкіндіктерді символдық түрде 800→350 және 800→503 деп белгілейік. Құмыраларға виноны құюдың әртүрлі мүмкіндіктерін (х,у,z) үштігімен немесе қысқаша хуz деп белгілейміз. Мұндағы х – 8 литрлік құмырадағы вино, у–5 литрлік құмырадағы вино және z – 3 литрлік құмыраға құйылатын вино. 350 жағдайында 3 түрлі құю мүмкіндігі бар: 350→323, 350→053, 350→800. Осындай ситуацияларға талдау жасай келе және құмыраларды түрліше толтыра отыра суретте көрсетілгендей бағытталған граф аламыз. Алынған графтың төбелері ретінде әртүрлі жағдайларды сипаттайтын үштіктер ал виноны түрліше құюлар доғаларға сәйкес келеді. Әрине, бұлграфта еселі доғалар жоқ, яғни бұл диграф. Жалпы, ең қысқа маршрутты анықтау есептеріндегі графтарда ілгектер мен еселі қабырғалар (доға) жоқ деп алынады. 800 төбеден 440 төбесіне апаратын маршрут табылса есеп шешілді деп есептейміз. Суреттен мұндай жол оңай табылатындығын көреміз: 800, 350, 323, 620, 152, 143, 440. Бұл жолға есептің шешімін беретін төмендегідей құюлар сәйкес келеді.

Вино 8 литрлік құмырадан 5 литрлік құмыраға толтырылады.

1-Сурет. Түрлі жағдайлар мен құюлар графы.

Содан кейін 5 литрлік құмырадан вино 3 литрлік құмыра толғанға дейін құйылады. 3 литрлік құмырадан вино түгелдей 8 литрлікке құйылады. 5 литрліктегі 2 литр 3 литрлікке құйылады. 8 литрліктегі 5 литрлікке толтырылады. 5 литрліктен 1 литрді 8 литрлік құмыраға құю керек (толғанға дейін). Соңында 3 литрліктен барлық виноны 8 литрлік құмыраға құйылады. Нәтижесінде 8 литрлік құмырада 4 литр вино және сонша литр 5 литрлік құмырада болады. Вино тең бөлінді.

Осы 800 төбеден  440 төбеге апаратын жол ең қысқа болады. Бұл жолды графтардағы ең қысқа маршрутты анықтайтын алгоритмді пайдаланып та табуға болады. Енді осы алгоритмнің жұмысын формальды түрде сипаттап көрейік:

Алгоритмнің жұмысы барысында х₀=800 алғашқы төбеден бірдей қашықтықтағы төбелер жиыны құрылады. Бұл жиындарды вертикаль түзулер яғни ярустарға (2 сурет) орналастырамыз (2-сурет). Нөлінші яруста бір ғана х₀=800 төбесі орналасқан. Бірінші яруста 800-ден шығатын доғалар кіретін төбелер орналасқан (350 және 503). Екінші ярусқа 350 және 503 төбелерге сыбайлас, бірақ 0-ші немесе 1-ші ярустарға кірмейтін төбелерді белгілейміз. Егер k-шы ярус құрылған болса (k+1)-ярусқа G графының алдыңғы ярустарда жоқ және k-шы ярустағы төбелерге сыбайлас төбелерді енгіземіз. Ярус құру у₀=440 төбесі алынған сәтте тоқталады.

Осыдан кейін құрылған графтың у₀=440 төбесінен х₀=800 төбесіне қайту барысында маршрутты анықтаймыз. Бұл маршрутпен кері жүру барысында х₀=800 төбесінен у₀=440 төбесіне апаратын ең қысқа жол табылады.

2-сурет