Problema grafuri (matricea costurilor / drumuri)

[•IdemLaFel]

Buna ziua ! Am o problema de facut la informatica. Profesoara a zis ca se face cu ajutorul algoritmului matricei costurilor, adica algoritmul lui Roy-Floyd. Eu insa nu prea ma descurc, e prea complexa problema pentru mine... ar putea sa ma ajute cineva ?

PROBLEMA:
O firma trebuie sa colecteze ambalaje din mai multe puncte de lucru din oras, fiecare punct de lucru gasindu-se pe o anumita strada. O retea de intersectii leaga direct unele dintre aceste puncte de lucru si intre oricare doua puncte de lucru exista o legatura prin intermediul traficului pe strazi. Traficul intre doua intersectii nu este intotdeauna in ambele sensuri, dar intre oricare doua intersectii exista trafic prin intermediul altor intersectii. Cantitatea de ambalaje care poate fi colectata intre doua intersectii intre care exista trafic direct este masurata in kilograme.

Scrieti un program care sa gaseasca un traseu optim intre doua intersectii A si B astfel incat o masina care pleaca din intersectia A si trebuie sa ajunga in intersectia B sa colecteze o cantitate cat mai mare de ambalaje. Datele se citesc dintr-un fisier astfel: de pe primul rand, numarul de intersectii, iar de pe urmatoarele randuri, triplete de numere x,y,c care semnifica faptul ca intersectia x este legata direct de intersectia y prin traficul de pe o strada de pe care se poate colecta cantitatea c de ambalaje. Etichetele intersectiilor A si B se citesc de la tastatura.
_____
Nu am nevoie de algoritmul cu citire si afisare din fisier. Are cineva o idee ? Cum se incepe, cum se desfasoara, ce conditii sa pun, care e logica problemei ? Multumesc anticipat !

[•Mitza444]

Poti incerca si cu Roy-Floyd,ai algoritmul descris aici:https://infoarena.ro/problema/royfloyd
Doar trebuie modificat putin pt. ca el gaseste costu minim,iar tie iti trebuie costul maxim.
Ca alternative poti incerca si:
1)Algoritmul lui Dijkstra:https://infoarena.ro/problema/dijkstra
2)Algoritmul Bellman-Ford:https://infoarena.ro/problema/bellmanford
Succes!

[•IdemLaFel]

au si codul c++, ca nu-l gasesc ?

[•mihai_florea]

Poti incerca si cu Roy-Floyd,ai algoritmul descris aici:https://infoarena.ro/problema/royfloyd
Doar trebuie modificat putin pt. ca el gaseste costu minim,iar tie iti trebuie costul maxim.
Ca alternative poti incerca si:
1)Algoritmul lui Dijkstra:https://infoarena.ro/problema/dijkstra
2)Algoritmul Bellman-Ford:https://infoarena.ro/problema/bellmanford
Succes!

Daca problema iti cere costul maxim, atunci devine NP-Hard. Nu cred ca exista o solutie mai buna decat sa folosesti backtracking. Vezi si http://en.wikipedia.org/wiki/Longest_path_problem

[•PlayLikeNeverB4]

Nu poti nega costurile si apoi afli costul minim?

[•mihai_florea]

Nu poti nega costurile si apoi afli costul minim?

NU
Algoritmul lui Dijkstra merge doar pentru costuri >= 0, iar Bellman-Ford sau Royfloyd merg atunci cand nu exista cicluri de cost < 0.

[•PlayLikeNeverB4]

Pai daca exista ciclu de cost negativ raspunsul e infinit. In caz contrar, e ok.

[•mihai_florea]

Pai daca exista ciclu de cost negativ raspunsul e infinit. In caz contrar, e ok.

Daca vrei sa privesti problema asa, ai dreptate. Dar, in general, se cere determinarea unui drum simplu (in care fiecare nod apare cel mult o data) de cost maxim. Iar aceasta problema se poate rezolva cu backtracking, dar nu se poate rezolva cu unul din algoritmii de cost minim in graf mentionati.

[•IdemLaFel]

din pacate nu pot folosi backtracking-ul pentru ca nu l-am invatat la scoala. oricum, nu trebuie decat sa aflu drumul MAXIM de la nodul A la nodul B, intr-un graf orientat...

[•AlexandruValeanu]

Se face cu Roy-Floyd si schimbi testul de verificare cu ceva de genul if cost[j] < cost[k] + cost[k][j]....