Fun with Dijkstra’s algorithm! Solution

Dijkstra’s algorithm!

In this project you will implement Dijkstra’s algorithm! for an undirected weighted graph. As part of this project you will gain some experience with working with libraries. All in all, you will need to write less than 40 lines of code, of which only 25 or so are doing something other than initializing variables or copying the results to pass back.

You should not modify any of the class de nitions in any of the .hpp les. Your code should be placed in a le named path.cpp, the skeleton of which is provided to you.

implementing Dijkstra’s algorithm!

The textbook version of Dijkstra’s algorithm! has two features that are annoying.

    1. All of the vertices are enqueued at the beginning, which leads to an unnecessarily large queue.

    2. In the priority queue we must be able to look up items in the queue and change their priority. This is not a standard feature of priority queues (and is not possible with the standard C++ priority queue.

In this implementation, I suggest the following.

    1. Enqueue vertices only as needed, rather than all at the start. This will lead to sub-stantially shorter priority queues.

    2. Rather than try to change the priorities of items already in the queue, just re-enqueue the same vertex with the updated priority. While this means that some vertices will end up in the queue more than once, the old values will be ignored and with any luck the queue won’t get too big.

This leads to an algorithm that looks like the following.


d i s t [ s ]
=
0
s g











for
a l l
v
2 Vf












d i s t [ v ]
= 1












S = ;















add
( s ,
d i s t [ s ] )
to
Q,
a min
p r i o r i t y  queue
u s i n g
d i s t [ s ]
to
rank  terms
while  (Q 6= ;)  and
( a n o t h e r
c o n d i t i o n  you
need  to  check )


u = t h e
v e r t e x
i n
Q
with
minimum
d i s t [ q ]




pop
u
o f f  Q












for
a l l
n e i g h b o r s
v
o f  u
//
Apply
r e l a x a t i o n
t o  t h e
n e i g h b o r s .

i f

( d i s t [ v ] > d i s t [ u ]
+
w e i g h t ( u , v ) )
//
New  s h o r t e s t
p a t h
found .


d i s t [ v ] = d i s t [ u ] + w e i g h t ( u , v )







add
( v ,
d i s t [ v ] )
to Q








In this pseudocode, weight(u,v) is the weight of the edge connecting u and v.

You will need to enqueue pairs (v, dist[v]), where v is a vertex and dist[v] is the most recent estimate of the distance from the source. You can either use the vertex distance class in graph.cpp or roll your own approach.


the code you are given

You should look in the header les to understand what are the various class objects and methods available to you and what they do. There is a sample driver main.cpp which takes a single argument on the command line, the name of a le of weighted edges to read. If the executable is named foo, then

> foo cal.in

reads the edges from the le cal.in. The edges appear one per line, with the two endpoints of the edge followed by the weight.

The library libgraph.a is a Linux archive le that contains the object les for most of the class methods involved. The make le Makefile will link against these. Since libgraph.a is a Linux archive, you will need to be on a Linux machine to link against it. Look in Makefile to see how the library is used.

In practice, one builds libraries of unchanging code rather than recompiling the code repeatedly. The use of library les also means we need not distribute source code everywhere.

the data    les you are given

There are several test graphs included. Some are simple:

square.in, where the vertices form a square,

chain.in, where the vertices form a one-dimensional chain,

disconnected.in, where two of the vertices are unreachable from the others. Two larger les are representations of part of the roads in California:

cal.in, which was the original le; I have no idea what the weights mean (they are not miles, kilometers, yards, meters, or spherical radians; maybe hecto-rods?),

cal.gc, where I have replaced the original weights with great circle distances (in miles) between vertices.

what to turn in, and how

The    le path.cpp will contain your implementation of the method

dijkstra results Weighted Graph::dijkstra (Vertex s).


Inside your cs303 git repository you should create a new directory named paths. This will be the folder for this project. You should add and commit the your path.cpp to the repository.

This is the tree structure your repository cs303 should have when you are done. Leaves are les and all the other nodes are directories:





cs303






hello

world
array
sorting
union

find
paths





















array.cpp
sort.hpp









main.cpp







hello.cpp

main.cpp
union

find.cpp
path.cpp

valgrind.txt
























array.cpp.gcov valgrind.txt

I will pull your code from gitlab.com (make sure you shared cs303 with me!) to grade.

grading

No credit will be given for

code that does not compile and link, code that opens any les,

code that includes an active main(),

code that writes any output (so be sure to disable any debugging output).

Here are things that will have a negative e ect on your grade, more or less in decreasing order of severity.

Your program crashes during testing. Code that is incorrect.

Code that appears to work but nevertheless has memory access errors. Memory leaks.

Code that is unnecessarily ine  cient.