Last homework for the Algorithm Design course at DSSC a.y. 2019/2020
29/06/2020
I implemented Dijkstra's algorithm by arrays. I represented the graph as an array of nodes with a dense Adjacency matrix, which in this case it is a density matrix. I reused the code from the Strassen Algorithm, and I assumed that negative weights presumed no connection(so
The execution time of this code should then be
Then I implemented it by heaps. The execution time of this code should then be
The heap implementation is slightly better than the array one.
In the test folders I tested the graph we had on Lecture.