DFS by Gautam Saini and Shilpi FNU

Optimized path finding between two locations/cities from a given graph using depth first method.

Run script using "python main.py" then

1. Enter initial location: (eg A1)
2. Enter final location: (eg G1)

Observe the outcomes. First path is traced in alphanumeric order and other 4 path are chosen from 2n possible path combinations where n is number of nodes of the given graph.

List of cities:

['A5', 'A4', 'A2', 'A1', 'B1', 'B2', 'B3', 'B4', 'B5', 'C2', 'C3', 'C4', 'C5', 'D1', 'D2', 'D3', 'D4', 'D5', 'E4', 'E5', 'F1', 'F2', 'F5', 'G1', 'G2', 'G2b', 'G4', 'G4b', 'G5']

Enter Initial location: A1

Enter Final location: G1

_____________________________________________________________

DFS path tracing alphanumeric order: ['A1', 'A2', 'A4', 'A5', 'C5', 'B5', 'B4', 'C4', 'C3', 'B2', 'B1', 'D1', 'D2', 'F2', 'E4', 'D4', 'D5', 'F5', 'E5', 'G4b', 'G2b', 'G2', 'G1']

A1 to A2 length: 130.0

A2 to A4 length: 305.0

A4 to A5 length: 90.0

A5 to C5 length: 306.0

C5 to B5 length: 229.16587878652442

B5 to B4 length: 36.05551275463989

B4 to C4 length: 96.0

C4 to C3 length: 155.72411502397438

C3 to B2 length: 131.21737689803132

B2 to B1 length: 113.0

B1 to D1 length: 231.0

D1 to D2 length: 126.0

D2 to F2 length: 162.00308639035245

F2 to E4 length: 303.03300150313663

E4 to D4 length: 137.01459776242822

D4 to D5 length: 100.0

D5 to F5 length: 263.0

F5 to E5 length: 81.78630692236935

E5 to G4b length: 140.41723540933285

G4b to G2b length: 231.0

G2b to G2 length: 27.018512172212592

G2 to G1 length: 102.0

Total alphanumeric DFS path length: 3496.4356236230024

_____________________________________________________________

Tracing alternative 4 DFS path in total available combination: 536870912

Alternative Path 1: ['A1', 'B1', 'B2', 'C2', 'C3', 'C4', 'B4', 'B5', 'A4', 'A5', 'C5', 'D5', 'D4', 'E4', 'E5', 'F5', 'G5', 'G4', 'G2', 'G1']

A1 to B1 length: 177.0

B1 to B2 length: 113.0

B2 to C2 length: 51.0098029794274

C2 to C3 length: 127.27922061357856

C3 to C4 length: 155.72411502397438

C4 to B4 length: 96.0

B4 to B5 length: 36.05551275463989

B5 to A4 length: 97.082439194738

A4 to A5 length: 90.0

A5 to C5 length: 306.0

C5 to D5 length: 102.0

D5 to D4 length: 100.0

D4 to E4 length: 137.01459776242822

E4 to E5 length: 110.47624178980746

E5 to F5 length: 81.78630692236935

F5 to G5 length: 96.0

G5 to G4 length: 191.0

G4 to G2 length: 232.0

G2 to G1 length: 102.0

Path length: 2401.428237040963

_____

Alternative Path 2: ['A1', 'A2', 'B2', 'B1', 'D1', 'D2', 'C2', 'C3', 'C4', 'B4', 'B5', 'C5', 'D5', 'D4', 'E4', 'E5', 'F5', 'G5', 'G4', 'G2', 'G1']

A1 to A2 length: 130.0

A2 to B2 length: 177.81451009408653

B2 to B1 length: 113.0

B1 to D1 length: 231.0

D1 to D2 length: 126.0

D2 to C2 length: 180.3995565404749

C2 to C3 length: 127.27922061357856

C3 to C4 length: 155.72411502397438

C4 to B4 length: 96.0

B4 to B5 length: 36.05551275463989

B5 to C5 length: 229.16587878652442

C5 to D5 length: 102.0

D5 to D4 length: 100.0

D4 to E4 length: 137.01459776242822

E4 to E5 length: 110.47624178980746

E5 to F5 length: 81.78630692236935

F5 to G5 length: 96.0

G5 to G4 length: 191.0

G4 to G2 length: 232.0

G2 to G1 length: 102.0

Path length: 2754.7159402878838

_____

Alternative Path 3: ['A1', 'B1', 'B2', 'C2', 'C3', 'C4', 'B4', 'B5', 'C5', 'D5', 'D4', 'E4', 'E5', 'F5', 'G5', 'G4', 'G2', 'G1']

A1 to B1 length: 177.0

B1 to B2 length: 113.0

B2 to C2 length: 51.0098029794274

C2 to C3 length: 127.27922061357856

C3 to C4 length: 155.72411502397438

C4 to B4 length: 96.0

B4 to B5 length: 36.05551275463989

B5 to C5 length: 229.16587878652442

C5 to D5 length: 102.0

D5 to D4 length: 100.0

D4 to E4 length: 137.01459776242822

E4 to E5 length: 110.47624178980746

E5 to F5 length: 81.78630692236935

F5 to G5 length: 96.0

G5 to G4 length: 191.0

G4 to G2 length: 232.0

G2 to G1 length: 102.0

Path length: 2137.5116766327496

_____

Alternative Path 4: ['A1', 'A2', 'A4', 'B5', 'B4', 'C4', 'C3', 'B2', 'B1', 'D1', 'D2', 'F2', 'E4', 'D4', 'D5', 'F5', 'E5', 'G4b', 'G2b', 'G2', 'G1']

A1 to A2 length: 130.0

A2 to A4 length: 305.0

A4 to B5 length: 97.082439194738

B5 to B4 length: 36.05551275463989

B4 to C4 length: 96.0

C4 to C3 length: 155.72411502397438

C3 to B2 length: 131.21737689803132

B2 to B1 length: 113.0

B1 to D1 length: 231.0

D1 to D2 length: 126.0

D2 to F2 length: 162.00308639035245

F2 to E4 length: 303.03300150313663

E4 to D4 length: 137.01459776242822

D4 to D5 length: 100.0

D5 to F5 length: 263.0

F5 to E5 length: 81.78630692236935

E5 to G4b length: 140.41723540933285

G4b to G2b length: 231.0

G2b to G2 length: 27.018512172212592

G2 to G1 length: 102.0

Path length: 2968.3521840312155

_____