Praktikum 6

Graaf

Koostage meetod graafis pikima tee leidmiseks. Pikima tee pikkus on võrdne Floyd-Warshalli algoritmiga leitud lühimate teepikkuste maatriksi suurima elemendi väärtusega. Pikima tee alguse ja lõpu määravad selle elemendi rea- ja veeruindeks.
Pikim tee ise leidke Dijkstra algoritmi abil. Pikim tee esitage kaarte (Arc) loendi kujul.

Näide graafist, mille pikima tee alguspunkt on v3 ja lõpp-punkt v5:

Extreme points: v3 v5
4 arcs: av3_v7 av7_v2 av2_v6 av6_v5 
shortest paths:
3 v1 v9 v7 v3 
2 v2 v7 v3 
0 v3 
2 v4 v7 v3 
4 v5 v6 v2 v7 v3 
3 v6 v2 v7 v3 
1 v7 v3 
3 v8 v9 v7 v3 
2 v9 v7 v3 

G
v1 3 --> av1_v9 1(v1->v9) 
v2 2 --> av2_v7 1(v2->v7)  av2_v6 1(v2->v6)  av2_v4 1(v2->v4) 
v3 0 --> av3_v7 1(v3->v7) 
v4 2 --> av4_v2 1(v4->v2)  av4_v7 1(v4->v7) 
v5 4 --> av5_v6 1(v5->v6) 
v6 3 --> av6_v2 1(v6->v2)  av6_v5 1(v6->v5)  av6_v9 1(v6->v9) 
v7 1 --> av7_v2 1(v7->v2)  av7_v3 1(v7->v3)  av7_v4 1(v7->v4)  av7_v9 1(v7->v9) 
v8 3 --> av8_v9 1(v8->v9) 
v9 2 --> av9_v1 1(v9->v1)  av9_v6 1(v9->v6)  av9_v7 1(v9->v7)  av9_v8 1(v9->v8)

Jaanus Pöial