Digraph’da negativ weight’lar

Ushbu maqolada biz negativ (manfiy) weight’larning graph’da shortest path’ni topishdagi ta’sirini ko’rib chiqamiz. Avvaldan aytib o’tish kerakki, negativ weight’lari bor graph’lar uchun bir ko’rib o’tgan Dijkstra algoritmi ishlamaydi.

Greedy algoritmi

Minimum spanning tree (MST) algoritmlarini boshlashdan avval biz ular uchun umumiy algoritm – Greedy algoritmi nazariyasini ko’rib chiqamiz. Greedy har bir qadamda optimal variantni tanlab, muammoni yechishning optimal yo’lini topishga urinadi.

Minimum spanning tree

Minimum spanning tree (MST) – undirected graph’dagi barcha o’zaro bog’langan vertex’larni o’z ichiga olgan (spanning) va aylana bo’lmagan (acyclic) sub-graph’lar ichidan minimum weight’li sub-graph.