Dasturchi, frilanser, gik va introvert
Maximum flow’ni topish jarayonida, ba’zida yechimga erishish uchun allaqachon berilgan flow’ni kamaytirish hisobiga boshqa (parallel) edge’da flow’ni oshiriladi. Inson ko’zi bilan ko’rib, qaysi flow’ni kamaytirish, qaysi flow’ni oshirishni o’zi aniqlab olishi mumkin, lekin kodda nima qilishni qanday ifodalaymiz?
Avvalgi maqolada maximum flow allaqachon topilgan graph’ni ko’rib o’tdik. Endi flow’ni qanday hisoblash haqida so’z yuritamiz.
Graph processing masalalarini o’rganishni davom ettiramiz. Minimum cut – graph’ni ikkiga shunday bo’lish kerakki, uning bo’linish edge’lari bir-biriga eng kam (kuchsiz) bog’langan joyi bo’lsin. Oddiyroq aytganda, graph’ni ikkiga bo’lish uchun eng kam harajat / kuch talab etilsin.
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.
Javascriptda o’zgaruvchi e’lon qilinganda unga ikki turdagi qiymatdan biri beriladi – primitive va reference qiymatlar. Agar qiymat number, string, boolean, undefined, null, or symbol tiplardan biri bo’lsa, u primitive qiymat; object, array, function – reference qiymat hisoblanadi.
Javascript ES2015 (yoki ES6) da o’zgaruvchi e’lon qilishning ikki yangi yo’li qo’shilgan – const va let. Ushbu maqolada biz var, let va const haqida so’z yuritamiz.
Endi biz DAGlar (directed acyclic graph) uchun shortest path’ni topishni ko’rib chiqamiz. Aslida DAGlar uchun Dijkstra’ning algoritmi ham ishlayveradi, ammo bizdagi graph’ning acyclic, ya’ni aylanasi yo’q ekanligini bilar ekanmiz, bu bizga shortest path’ni topish ishini yengillashtiradimi?
Dijkstra’ning algoritmi graph’dagi bir vertex’dan boshqa har bir vertex’ga qisqa yo’lni topish uchun ishlatiladi.
Biz o’tgan mavzularda ko’rib o’tganimiz, minimum spanning tree – edge’lari weight’ga ega undirected graph’dagi barcha vertex’larni o’z ichiga olgan qisqa yo’lni topishga bag’ishlangan edi. Edge-weight’li directed graph uchun esa shortest path (qisqa yo’l) algoritmlari bilan tanishib chiqamiz.
Minimum spanning tree’ni topishning yana bir klassik algoritmlaridan biri – Prim algoritmi ishlash tartibi quyidagicha…