Testing Procedure stuff n things. - dcobbley/AlgorithmsProject350 GitHub Wiki

2/20/15 Comparing MIT Dijkstra vs MIT Bellman-Ford Testing Procedure:

• Range of Input
• Sample Input
• Implementation(source Code) - pseudo code

1. Found some code examples for Dijkstra's: http://rosettacode.org/wiki/Dijkstra%27s_algorithm
2. Code for Dijkstra's with a write up: http://en.literateprograms.org/Dijkstra%27s_algorithm_%28C_Plus_Plus%29
3. Princeton is trying to solve all of our problems... http://algs4.cs.princeton.edu/44sp/
4. Python: http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Python

Metrics:

• Clock time (not by itself)
• What other metrics??
• Linux tools for analyzing

1. Possibility, links to a tool called igraph which says it includes Dijkstra's and B-F (uses C or Python): http://stackoverflow.com/questions/3038661/efficiently-finding-the-shortest-path-in-large-graphs/3040843#3040843
2. GPROF, Ptrace, Ltrace are all tools for different metrics.
3. Python tools: http://www.huyng.com/posts/python-performance-analysis/

EXTRAS. Literature:

• 4 relevant sources

1. http://goo.gl/o1F9ic (links to the articles wiki)
2. http://library.pdx.edu/dofd/subjects/12 (CS resources)

---

What other questions are we left with

• Does modified Dijkstras take negative weights?
• How much to focus on space complexity?