Algoritmlarni Tuzulishi: 1.Biz hozir massivni elementlar sonii topamiz.
2.Massiv bir elementidan ikkinchi elementiga boradigan yollar hamma kambinatsiyalarni korib chiqamiz.
3.Hamma kobinatsiyalar ichidan saralash algoritmi tuzamuz.
4.Agar biz bergan yollar ichida eng kam tuguni bolgani eng qisqa yoli boladi.
5.Berilgan natijani ekranga chiqaramiz.
6.Dastur yakunlandi.
Graflarni dasturda amaliy korinishi qudagicha boladi yani bu Python dasturlash Tilida yozildi.
Dasturni kodi def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
Javobi: find_shortest_path(graph, 'A', 'D') ['A', 'C', 'D']
Расмда А, Б, В, Г, Д, Е - шаҳарларини боғлайдиган йўлларнинг диаграммаси кўрсатилган. Ҳар бир йўл бўйлаб фақат битта йўналишда ҳаракат қилиш мумкин, бу стрелка орқали кўрсатилган. А шаҳардан Е шаҳарга боришга неча хил йўл мавжуд?
1 вазифа Эътибор беринг, Е-шаҳрига борадиган йўллар сони Ж, Г ва Д шаҳарларига борадиган йўллар йиғиндисидир. Ж шаҳрига борадиган йўллар сони Г ва Б шаҳарларига борадиган йўллар йиғиндисидир. Шундай қилиб:
Г = Б + В
Д = Г + В
Ж = Б + Г
Е = Ж + Г + Д
Эътибор беринг, Б ва В нуқталарига ягона йўл билан - А шаҳридан бориш мумкин. Биз расмда ҳар бир нуқтанинг тепасида индекслар билан белгилаймиз. Унга эришиш ва жами ҳисоблаш учун ишлатилиши мумкин бўлган йўллар сони.
Жавоб: 8
Ko‘rishimiz mumkinki, agar belgilashlarga e’tibor berilmasa, G va H graflarni bir xil rasmda tasvirlash mumkin. Bu esa, ushbu graflarning bittasi uchlarini shunday qayta belgilash mumkinki, graflar teng bo‘lib qoladi. Bunday graflar izomorf graflar deyiladi.
