Description
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.
-
Graph representations:
-
-
Implement a class for sparse graphs;
-
-
-
Implement a class for dense graphs;
-
In each case implement at least the following methods:
-
• AddEdge
• RemoveVertex
• SetEdgeWeight
• RemoveEdge
• IsAdjacent1
• GetVertexValue
• AddVertex
• GetEdgeWeight
• SetVertexValue
-
Implement Dijkstra algorithm (3.??) using Fibonacci heaps;
-
Bellman-Ford (algorithm 3.??);
-
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.
