AMcoder - javascript, python, java, html, php, sql

Ի՞նչ փոփոխություններ կարող եք անել գրաֆիկում, որպեսզի թույլատրեք Դեյկստրայի ալգորիթմն աշխատել դրա վրա:

Այսպիսով, ես մտածում էի, առանց մեկ այլ ալգորիթմի դիմելու, ի՞նչ փոփոխություններ կարող եք կատարել գրաֆիկում, որպեսզի Դեյկստրայի ալգորիթմը աշխատի դրա վրա, և այնուամենայնիվ ստանա ճիշտ պատասխանը օրվա վերջում: Եթե ​​դա նույնիսկ հնարավոր է ընդհանրապես:

Ես նախ մտածեցի ավելացնել հաստատուն, որը հավասար է ամենաբացասական քաշին բոլոր կշիռներին, բայց ես գտա, որ դա կխառնի ամեն ինչ և կփոխի սկզբնական մեկ աղբյուրի ուղին:

Այնուհետև ես մտածեցի անցնել գրաֆիկի միջով, զրոյից փոքր բոլոր կշիռները դնել մի զանգվածի կամ նման մի բանի մեջ և այնուհետև այն բազմապատկել -1-ով: Կարծում եմ, որ նա կաշխատի (չհաշված ժամանակի սահմանափակումները), բայց միգուցե ես սխալ ձևով եմ նայում:

Խմբագրել. Մեկ այլ գաղափար. Ինչ կասեք բոլոր բացասական կշիռները մշտապես դնելու անսահմանության վրա: այդ կերպ ապահովելով, որ դրանք անտեսվեն:

Այսպիսով, ես պարզապես ուզում եմ լսել որոշ կարծիքներ այս մասին. ինչ եք կարծում տղաներ

graph algorithm shortest-path dijkstra
13.05.2012

  • Իրական հարցն այն է, թե ինչ է նշանակում բացասական եզրերով (կամ նույնիսկ ավելի վատ` բացասական ցիկլերով) գրաֆիկի ամենակարճ ճանապարհը: 13.05.2012
  • @Shahbaz Բացասական կշիռները բարդ են, բայց ես ենթադրում եմ, որ դա նշանակում է այն, ինչ սովորաբար նշանակում է. ամենակարճ ճանապարհը ներառյալ բոլոր նվազեցված ծախսերը (բացասական կշիռները): Այո, դա այնքան էլ իմաստ չուներ: 13.05.2012

Պատասխանները:


1

Կարծես դուք փնտրում եք Ջոնսոնի ալգորիթմի նման մի բան.

  1. Նախ, գրաֆիկին ավելացվում է նոր q հանգույց՝ զրոյական քաշի եզրերով միացված մյուս հանգույցներից յուրաքանչյուրին։

  2. Երկրորդ, Բելման-Ֆորդի ալգորիթմն օգտագործվում է, սկսած q նոր գագաթից, յուրաքանչյուր v գագաթի համար գտնելու համար q-ից v ուղու նվազագույն քաշը h(v): Եթե այս քայլը հայտնաբերում է բացասական ցիկլ, ապա ալգորիթմը կավարտվի: .

  3. Այնուհետև սկզբնական գրաֆիկի եզրերը վերակշռվում են՝ օգտագործելով Բելման-Ֆորդի ալգորիթմի կողմից հաշվարկված արժեքները. u-ից v եզրին, որն ունի w(u,v) երկարություն, տրվում է նոր երկարություն w(u,v) + h(: u) − h(v).

  4. Վերջապես, q-ը հանվում է, և Դեյկստրայի ալգորիթմն օգտագործվում է վերակշռված գրաֆիկի յուրաքանչյուր հանգույցից մինչև մյուս գագաթը գտնելու ամենակարճ ուղիները։

Ցանկացած ալգորիթմով դուք պետք է ստուգեք բացասական ցիկլեր, իսկ եթե բացասական ցիկլ չկա, գտեք ամենակարճ ճանապարհը:

Ձեր դեպքում դուք պետք է մեկ անգամ գործարկեք Dijkstra-ի ալգորիթմը: Նաև նշեք, որ Ջոնսոնի կիսամյակային ալգորիթմում Bellman–Ford ալգորիթմն աշխատում է միայն նոր ավելացված հանգույցի համար: (ոչ բոլոր գագաթները):

13.05.2012
  • Կոռեկտության ապացույցը կարող եք գտնել վիքի հղումում։ Բայց եթե կա որևէ երկիմաստություն, կարող եմ բացատրել: 13.05.2012
    • Նոր նյութեր
    Օգտագործելով Fetch Vs Axios.Js-ը՝ HTTP հարցումներ կատարելու համար
    JavaScript-ը կարող է ցանցային հարցումներ ուղարկել սերվեր և բեռնել նոր տեղեկատվություն, երբ դա անհրաժեշտ լինի: Օրինակ, մենք կարող ենք օգտագործել ցանցային հարցումը պատվեր ներկայացնելու,..
    Տիրապետել հանգստության արվեստին. մշակողի ուղեցույց՝ ճնշման տակ ծաղկելու համար
    Տիրապետել հանգստության արվեստին. մշակողի ուղեցույց՝ ճնշման տակ ծաղկելու համար Ինչպե՞ս հանգստացնել ձեր միտքը և աշխատեցնել ձեր պրոցեսորը: Ինչպես մնալ հանգիստ և զարգանալ ճնշման տակ...
    Մեքենայի ուսուցում բանկային և ֆինանսների ոլորտում
    Բարդ, խելացի անվտանգության համակարգերը և հաճախորդների սպասարկման պարզեցված ծառայությունները բիզնեսի հաջողության բանալին են: Ֆինանսական հաստատությունները, մասնավորապես, պետք է առաջ մնան կորի..
    Ես AI-ին հարցրի կյանքի իմաստը, այն ինչ ասում էր, ցնցող էր:
    Այն պահից ի վեր, երբ ես իմացա Արհեստական ​​ինտելեկտի մասին, ես հիացած էի այն բանով, թե ինչպես է այն կարողանում հասկանալ մարդկային նորմալ տեքստը, և այն կարող է առաջացնել իր սեփական արձագանքը դրա..
    Ինչպես սովորել կոդավորումը Python-ում վագրի պես:
    Սովորելու համար ծրագրավորման նոր լեզու ընտրելը բարդ է: Անկախ նրանից, թե դուք սկսնակ եք, թե առաջադեմ, դա օգնում է իմանալ, թե ինչ թեմաներ պետք է սովորել: Ծրագրավորման լեզվի հիմունքները, դրա..
    C++-ի օրական բիթ(ե) | Ամենաերկար պալինդրոմային ենթաշարը
    C++ #198-ի ամենօրյա բիթ(ե), Ընդհանուր հարցազրույցի խնդիր. Ամենաերկար պալինդրոմային ենթատող: Այսօր մենք կանդրադառնանք հարցազրույցի ընդհանուր խնդրին. Ամենաերկար palindromic substring...
    Kydavra ICAReducer՝ ձեր տվյալների ծավալայինությունը նվազեցնելու համար
    Ի՞նչ է ICAReducer-ը: ICAReducer-ն աշխատում է հետևյալ կերպ. այն նվազեցնում է նրանց միջև բարձր փոխկապակցված հատկանիշները մինչև մեկ սյունակ: Բավականին նման է PCAreducer-ին, չնայած այն..