FilesExpand file tree

 master

/

tsp.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

65 lines (60 loc) · 2.07 KB

 master

/

tsp.py

Top

File metadata and controls

• Code
• Blame

65 lines (60 loc) · 2.07 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

# tsp.py

# From Classic Computer Science Problems in Python Chapter 9

# Copyright 2018 David Kopec

#

# Licensed under the Apache License, Version 2.0 (the "License");

# you may not use this file except in compliance with the License.

# You may obtain a copy of the License at

#

# http://www.apache.org/licenses/LICENSE-2.0

#

# Unless required by applicable law or agreed to in writing, software

# distributed under the License is distributed on an "AS IS" BASIS,

# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

# See the License for the specific language governing permissions and

# limitations under the License.

from typing import Dict, List, Iterable, Tuple

from itertools import permutations

vt_distances: Dict[str, Dict[str, int]] = {

"Rutland":

{"Burlington": 67,

"White River Junction": 46,

"Bennington": 55,

"Brattleboro": 75},

"Burlington":

{"Rutland": 67,

"White River Junction": 91,

"Bennington": 122,

"Brattleboro": 153},

"White River Junction":

{"Rutland": 46,

"Burlington": 91,

"Bennington": 98,

"Brattleboro": 65},

"Bennington":

{"Rutland": 55,

"Burlington": 122,

"White River Junction": 98,

"Brattleboro": 40},

"Brattleboro":

{"Rutland": 75,

"Burlington": 153,

"White River Junction": 65,

"Bennington": 40}

}

vt_cities: Iterable[str] = vt_distances.keys()

city_permutations: Iterable[Tuple[str, ...]] = permutations(vt_cities)

tsp_paths: List[Tuple[str, ...]] = [c + (c[0],) for c in city_permutations]

if __name__ == "__main__":

best_path: Tuple[str, ...]

min_distance: int = 99999999999 # arbitrarily high number

for path in tsp_paths:

distance: int = 0

last: str = path[0]

for next in path[1:]:

distance += vt_distances[last][next]

last = next

if distance < min_distance:

min_distance = distance

best_path = path

print(f"The shortest path is {best_path} in {min_distance} miles.")