Discrete optimization

129 words

Professor: Welcome back to Algorithms class. Today, we will cover Dijkstra’s shortest path algorithm, the core of all navigation software. Next week’s assignment is to write code to compute shortest paths in a number of real world instances.

Professor: Suppose we have a road network described by a graph with n vertices and m edges and a vector c \in \mathbb{R}^E assigning a travel time to every edge. We want to minimize total travel time, and –

Student: I have a question. What if we want to keep other things into account, like finding a simple route with few turns?

Professor: The formalism allows for that by changing the objective and graph. Anyway, so we want to minimize travel time and the first step is to [blah blah blah]

Leave a Reply