Algoritm distanta optima

[Zatarra]

Se dau urmatoarele puncte:

As dori sa veniti cu idei pentru aflarea distantei optime de a parcurge toate cele 5 puncte A,B,C,D,E.

Se stie ca plecarea e din start.. graful e bidirectional in toate nodurile mai putin START (deoarece acesta este punctul de plecare), se stiu distantele intre noduri (d(A,!=d(B,A) - un exemplu).

As dori o solutie in pseudocod daca se poate, o transpun eu in java, respectiv php.

Multumesc anticipat.

P.S. Nu veniti cu idei de genul aplica Greedy, aplica Dijkstra, aplica Floyd aplica nu stiu ce. Am nevoie strict pe exemplul acesta.

P.P.S. Eu m-am gandit la un backtrackig cu suma minima a distantelor.

[Xander]

la puncte asa putine nici nu se simte backtracku btw faza cu trecutul o singura data prin s poate sa fie ceva de genul shoot yourself in the leg

exemplu:

d(*,*) = 5

d(s,a) = 1

d(d|c,a) = 200

cel mai scurt ar fi s,a,s,...

ca sa scoti si cazul asta iti ti o matrice si marchezi arcele prin care ai trecut

m:
  s a b c d e
s   1
a 0
b
c
d
e
pas1: m[s,a] = 1
pas2: m[a,s] = 1
pas3: ... etc

si faci backtrack tratand toate arcele ca bidirectionale... sa poti sa mergi si s-> si a->s

[Zatarra]

Am gasit solutia, trebuie folosit algoritmul A* deoarece functia h am si e precisa (indeplineste toate conditiile pentru A*).

Mai ramane sa implementez.

Ms de raspuns Xander.