Računalništvo 2

Na vajah bomo najprej ponovili Dijkstrov algoritem (Kaj računa, predpostavke, algoritem, zahtevnost).

Nato bomo reševali naloge :

1) Simuliraj Dijkstrov algoritem na spodnjem grafu.

2) Napiši algoritem (v čim bolj python sintaksi) s katerim si rešil zgornji problem. Probaj napisat še algoritem z uporabo prioritetne vrste. Primerjaj časovne zahtevnosti teh dveh algoritmov in komentiraj v katerih primerih bi uporabil kater algoritem. Primerjaj še z FW algoritmom iz prejšnjih vaj.

3) Kako bi modificiral Dijkstrov algoritem, da bi poleg najcenejše vrnil še najkrajšo pot (ali kakšno drugo "sestavljeno" metriko")?

4) Poizkusi opustiti predpostavko o nenegativnih utežeh, tako da vsem povezavam prišteješ tako število, da postanejo nenegativne. Kje je glavni problem tega pristopa?

5) Probaj modificirat Dijkstro, da poišče najdaljšo pot. Kje je problem? Pokaži, da je problem najdaljše poti v grafu "zelo težak" (Namig: Hamiltonova pot). Za kakšne grafe bi lahko poiskali najdaljšo pot/poti? Kakšen algoritem bi tam uporabili?

6) Dijkstrov algoritem iz točke 1) in 2) implementiraj v pythonu. Kot vhod naj sprejme seznam povezav oblike (u, v, teza_uv). Poleg primera od zgoraj dodaj še kakšen svoj testni primer.