If this was a wiki, I wouldn't bother posting this, but since I'd want feedback on minor issues, I thought I'd summarize small problems I noted while reading this. These are all relatively minor issues, and the article is overall very useful.
- Section 1
- There is a spurious '"' in your "An example of a neighborhood of width 7 and height 5".
- line break between the definitions of 'Order' and 'Size' for readability
- in your Singly linked list data-structue
- you have named your field 'link', but in subsequent code you use both 'next' and 'link' when refering to this field.
- unless your type notation (using [node]) is a standard topcoder practice, it might lead to less confusion amongst readers if you removed the brackets:
// additional fields for data
- Your cost function is a little problematic, since intuitively it should return a number, yet yours often return either integers or strings. A little blurb to the effect that some special integer value (MAXINT, -1, etc.) has been reserved to represent infinite cost, and then using that value instead of the string "Not possible", would make your 'cost' functions more "sound".
- In your 'Graphs' section, the definition of your 'node' astructure might lead to some confusion. Although the intent is clear to people already somewhat familiar, it may not be so clear to those new to the ideas (to whom this article is targeted). First, you are defining 'neighbors' as a list of nodes (where a 'list' is a conceptual data-structure) but then treating it as just an array in your cost function (with the use of neighbor). Second, your 'cost' function is again somewhat type-ambiguous, seeing as how it returns Node instances sometimes, and strings others times, when it should really be returning a number. Might I suggest:
cost(X,Y) := if (X.neighbors contains Y at index i) return X.cost[i] else INF;
- Section 2
- All of your C++ code examples will confuse novices because < and > haven't been escaped.
- Section 3
- In the section entitled 'Dijkstra (Heap method)':
- Your assertions about heap complexity isn't true of all kinds of heaps. It is true of binary heaps, but not binomial or fibonacci or various other heaps (wikipedia has a good discussion on this).
- Just above the first code snippet, you say "...exccept substitute Heap in place of the Queue or Stack...", but then proceed to substitute 'priorityQueue' instead.