Project: Finding Optimal Routes

Total Points: $100$

Due: Friday, July $26,$ by $2359$ Central

If you like, you may work in teams of $2.$ Both teammates will receive the same grade. Please

carefully read the submission instructions at the end of the assignment.

Grader: Suravi Regmi $($sregmi$1$@memphis.edu$).$ Grades will generally be posted within $1-2$

weeks of the assignment due date. Questions about grading? Please contact her first.

The Story So Far...

The year is $2324.$ Humanity has managed to still be around and has recently joined the United

Federation of Spacefaring Civilizations. You$$ve been hired by the federation to write software for

their interstellar warp gate system, which connects various star systems in the universe together.

Each warp gate connects two systems together, but not every pair of systems is connected. For

example, there is no warp gate that directly connects Arcturus to Rigel, because the Arcturians

have had a longstanding feud with the Rigellians. However, there are gates connecting Arcturus to

Betelgeuse and Betelgeuse to Rigel, so it$$s possible to travel from Arcturus to Rigel with a $$layover$$

at Betelgeuse. Furthermore, each star system has its own economy and trade agreements with other

systems, so the cost of using each warp gate differs widely. The problem you want your software

to solve is this: given any two star systems in the universe, what$$s the least expensive way to get

from the starting point to the destination? People $($and other intelligent sentient organisms$)$ want

cheap flights even in $2324.$

$1$

COMP $2150-$ Summer $2024$ Project Due Friday, July $26,$ by $2359$ Central

Graphs

Mathematically, we can model the warp gate network as a graph. Each star system is represented

by a vertex in the graph. Vertices that are connected by warp gates have an edge between them.

Vertices that are directly connected by edges are known as neighbors. Each edge has a weight

representing the cost of using that warp gate. We$$ll assume that the gates are bidirectional, so if we

can travel from vertex A to vertex B$,$ we can also travel from B back to A at the same cost. The

fancy technical term for this kind of graph is a weighted undirected graph. We will also assume

that the graph is connected, meaning that it$$s possible to get from any vertex to any other vertex

$($albeit not necessarily directly$).$

Here$$s an example of a graph showing the connections between a few star systems. This graph

has four vertices and five edges.

Finding Shortest Paths

Dijkstra$$s algorithm, developed in the $1950$s by Earth computer scientist Edsger Dijkstra, gives

us a way to find the least expensive $($shortest$)$ path between any two vertices of a graph. Here$$s

how the algorithm works:

$1.$ Assign every vertex a distance of $\backslash$infty except the starting vertex, whose distance is $0.$ Mark

every vertex as $$unvisited$.$

$2.$ Pick the minimum$-$distance unvisited vertex from the graph. Call this vertex V $.$ Note that

initially, this will always be the starting vertex since it$$s the only one with a distance that$$s

not $\backslash$infty $.$

$3.$ Consider each of vertex V $$s unvisited neighbors. For each unvisited neighbor N :

$$ Compute N $$s $$tentative distance$$ by adding V $$s distance to the weight of the edge

connecting V and N $.$

Page $2$ of $11$

COMP $2150-$ Summer $2024$ Project Due Friday, July $26,$ by $2359$ Central

$$ If the tentative distance is less than N $$s current distance, replace N $$s distance with the

tentative distance. Also mark V as N $$s $$previous$$ vertex.

$$ If the tentative distance is not less than N $$s current distance, do nothing.

$4.$ Mark vertex V as $$visited$.$

$5.$ Go back to step $2$ and repeat until the destination vertex has been $$visited$.$ At this point, the

destination vertex$$s distance is the cost of the shortest path, and the path itself can be found

by following the $$previous$$ records from the destination backwards to the starting point.

For example, suppose we want to find the shortest path from Arcturus to Rigel in the previous

graph. Here$$s how Dijkstra$$s algorithm would run:

$1.$ Initialize every vertex$$s distance to $\backslash$infty except Arcturus, which has a distance of $0.$ Mark every

vertex as unvisited.

$2.$ Pick the minimum$-$distance unvisited vertex from the graph, which is Arcturus. Arcturus has

two unvisited neighbors, Betelgeuse and Eta Carinae.

$$ For Betelgeuse, the tentative distance is Arcturus$$ distance $(0)$ plus the weight of the

edge connecting Arcturus to Betelgeuse $(6)$: $0+6=6.6$ is less than Betelgeuse$$s current

distance $(\backslash$infty $),$ so we replace Betelgeuse$$s distance with $6$ and mark Betelgeuse$$s previous

as Arcturus.

Page $3$ of $11$

COMP $2150-$ Summer $2024$ Project Due Friday, July $26,$ by $2359$ Central

$$ For Eta Carinae, the tentative distance is Arcturus$$ distance $(0)$ plus the weight of

the edge connecting Arcturus to Eta Carinae $(10)$: $0+10=10.10$ is less than Eta

Carinae$$s current distance $(\backslash$infty $),$ so we replace Eta Carinae$$s distance with $10$ and mark

Eta Carinae$$s previous as Arcturus.

Page $4$ of $11$