Transport2

Soluţie 1
Pentru a afla costul de la nodul 1 la nodul N, vom utiliza algorimul lui Dijkstra puţin modificat. Astfel, vom reţine pentru fiecare nod, valoarea minimă între nodul 1 şi nodul respectiv. Când dorim să mergem în vecinii nodului curent trebuie verificat dacă min(costul_nodului_curent, costul_muchiei) > costul_nodului_vecin. Complexitatea acestui algoritm este O(M logN).

Soluţie 2
Vom căuta binar răspunsul între 1 şi valoarea maximă pe care o poate avea o muchie. Pentru o valoare fixată, vom considera doar muchiile cu valoarea mai mare sau egală cu valoarea fixată şi vom utiliza o parcurgere în adâncime pentru a vedea dacă nodurile 1 şi N sunt în aceeaşi componentă conexă. Complexitatea acestei soluţii este O((N + M)*log MaxVal).

Soluţie 3
Pentru fiecare valoare vom reţine ce muchii au valoarea respectivă. Apoi, vom itera prin toate valorile posibile începând de la cea maximă şi la fiecare pas vom uni nodurile care sunt legate prin muchia respectivă folosind structura mulţimi disjuncte. Ne vom opri în momentul în care nodurile 1 şi N sunt în aceeaşi componentă conexă, rezultatul fiind prima valoare pentru care nodurile 1 şi N se află în aceeaşi componentă conexă. Complexitatea acestei soluţii este O(M log*N).