Goals of the lab
• Course application
• Data sctructures
• Python Object Oriented Programming
Unless specified otherwise, all the programs are expected to be completed in Python or O’caml.
1. Graph representations:
(a) Implement a class for sparse graphs;
(b) Implement a class for dense graphs;
In each case implement at least the following methods:
• AddEdge
• RemoveVertex
• SetEdgeWeight
• RemoveEdge
• IsAdjacent1
• GetVertexValue
• AddVertex
• GetEdgeWeight
• SetVertexValue
2. Implement Dijkstra algorithm (3.??) using Fibonacci heaps;
3. Bellman-Ford (algorithm 3.??);
4. Compare the efficiency of Bellman-Ford and Dijkstra in terms of (i) complexity and (ii) running time;
1v.IsAdjacent(u) checks if vertices v and u are adjacent.
