Advanced Algorithms: Travelling Salesman Problem

September 13, 2019 • ☕️ 2 min read

The travelling salesman problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”

Travelling Salesman

Solution of a travelling salesman problem: the black line shows the shortest possible loop that connects every red dot.

Travelling Salesman Graph

TSP can be modelled as an undirected weighted graph, such that cities are the graph’s vertices, paths are the graph’s edges, and a path’s distance is the edge’s weight. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

/**
 * Get all possible paths
 * @param {GraphVertex} startVertex
 * @param {GraphVertex[][]} [paths]
 * @param {GraphVertex[]} [path]
 */
function findAllPaths(startVertex, paths = [], path = []) {
  // Clone path.
  const currentPath = [...path]

  // Add startVertex to the path.
  currentPath.push(startVertex)

  // Generate visited set from path.
  const visitedSet = currentPath.reduce((accumulator, vertex) => {
    const updatedAccumulator = { ...accumulator }
    updatedAccumulator[vertex.getKey()] = vertex

    return updatedAccumulator
  }, {})

  // Get all unvisited neighbors of startVertex.
  const unvisitedNeighbors = startVertex.getNeighbors().filter(neighbor => {
    return !visitedSet[neighbor.getKey()]
  })

  // If there no unvisited neighbors then treat current path as complete and save it.
  if (!unvisitedNeighbors.length) {
    paths.push(currentPath)

    return paths
  }

  // Go through all the neighbors.
  for (
    let neighborIndex = 0;
    neighborIndex < unvisitedNeighbors.length;
    neighborIndex += 1
  ) {
    const currentUnvisitedNeighbor = unvisitedNeighbors[neighborIndex]
    findAllPaths(currentUnvisitedNeighbor, paths, currentPath)
  }

  return paths
}

/**
 * @param {number[][]} adjacencyMatrix
 * @param {object} verticesIndices
 * @param {GraphVertex[]} cycle
 * @return {number}
 */
function getCycleWeight(adjacencyMatrix, verticesIndices, cycle) {
  let weight = 0

  for (let cycleIndex = 1; cycleIndex < cycle.length; cycleIndex += 1) {
    const fromVertex = cycle[cycleIndex - 1]
    const toVertex = cycle[cycleIndex]
    const fromVertexIndex = verticesIndices[fromVertex.getKey()]
    const toVertexIndex = verticesIndices[toVertex.getKey()]
    weight += adjacencyMatrix[fromVertexIndex][toVertexIndex]
  }

  return weight
}

/**
 * BRUTE FORCE approach to solve Traveling Salesman Problem.
 *
 * @param {Graph} graph
 * @return {GraphVertex[]}
 */
export default function bfTravellingSalesman(graph) {
  // Pick starting point from where we will traverse the graph.
  const startVertex = graph.getAllVertices()[0]

  // BRUTE FORCE.
  // Generate all possible paths from startVertex.
  const allPossiblePaths = findAllPaths(startVertex)

  // Filter out paths that are not cycles.
  const allPossibleCycles = allPossiblePaths.filter(path => {
    /** @var {GraphVertex} */
    const lastVertex = path[path.length - 1]
    const lastVertexNeighbors = lastVertex.getNeighbors()

    return lastVertexNeighbors.includes(startVertex)
  })

  // Go through all possible cycles and pick the one with minimum overall tour weight.
  const adjacencyMatrix = graph.getAdjacencyMatrix()
  const verticesIndices = graph.getVerticesIndices()
  let salesmanPath = []
  let salesmanPathWeight = null
  for (
    let cycleIndex = 0;
    cycleIndex < allPossibleCycles.length;
    cycleIndex += 1
  ) {
    const currentCycle = allPossibleCycles[cycleIndex]
    const currentCycleWeight = getCycleWeight(
      adjacencyMatrix,
      verticesIndices,
      currentCycle
    )

    // If current cycle weight is smaller then previous ones treat current cycle as most optimal.
    if (
      salesmanPathWeight === null ||
      currentCycleWeight < salesmanPathWeight
    ) {
      salesmanPath = currentCycle
      salesmanPathWeight = currentCycleWeight
    }
  }

  // Return the solution.
  return salesmanPath
}