ClassicComputerScienceProblemsInPython/Chapter9/tsp.py at master · DmitryShv/ClassicComputerScienceProblemsInPython · GitHub

History

65 lines (60 loc) · 2.07 KB

Raw

# tsp.py

# From Classic Computer Science Problems in Python Chapter 9

# 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.")

ClassicComputerScienceProblemsInPython/Chapter9/tsp.py at master · DmitryShv/ClassicComputerScienceProblemsInPython · GitHub

Expand file tree

Breadcrumbs

tsp.py

Latest commit

History

Breadcrumbs

tsp.py

File metadata and controls