3 ms·

> If am to be honest, I have forgotten how to implement the shortest route from using a directed graph from scratch. I've never known, because I've never had t

> If am to be honest, I have forgotten how to implement the shortest route from using a directed graph from scratch. I've never known, because I've never had to do it. What I do know is that I've read about Dijkstra's Algorithm solving a very similar problem. A quick Google leads me to Wikipedia, which has a section on specialized algorithms for directed graphs. This is the type of background information and research ability I would expect from a developer, not that they would necessarily be able to recite the correct algorithm and implement it without checking a reference.

AstralStorm 10y ago
Even for this, search engines are a good starting point. You might want to look for libraries under a suitable licence, for algorithms in both wiki and research papers, lastly in a book. If it is some implementation detail first docs then sources. If that fails, look for a blog (weirdness is often blogged about), only finally ask a friend. Stack Overflow (and Math Exchange) is a meagre source mostly useful for details and even then answers are very varying in quality, typically poor but a decent starting point for proper analysis. Never take a ready made solution without understanding its limitations and important details. I've seen poor or cruft libraries used where better ones existed. Also second guess pulling a big framework whole. Something like Boost might have many things, but they tend to have important shortcomings, so might not fit. (Say, their parser lib, concurrency extras, matrix math) Lastly if there is nothing useful, there are general ways to implement algorithms. If doing something yourself, take platform specifics into account if performance matters.
- LyndsySimon 10y ago
  In my experience, finding the right search terms is 80% of the battle. Knowing the phrase "Dijkstra's Algorithm" is a big leg up here, and would put me only one or two degrees of separation away from the correct answer. If I didn't know that term, then I'd search "shortest path directed graph". That leads to a Wikipedia article with links to a variety of algorithms.

AstralStorm 10y ago

Even for this, search engines are a good starting point. You might want to look for libraries under a suitable licence, for algorithms in both wiki and research papers, lastly in a book. If it is some implementation detail first docs then sources. If that fails, look for a blog (weirdness is often blogged about), only finally ask a friend. Stack Overflow (and Math Exchange) is a meagre source mostly useful for details and even then answers are very varying in quality, typically poor but a decent starting point for proper analysis. Never take a ready made solution without understanding its limitations and important details. I've seen poor or cruft libraries used where better ones existed. Also second guess pulling a big framework whole. Something like Boost might have many things, but they tend to have important shortcomings, so might not fit. (Say, their parser lib, concurrency extras, matrix math) Lastly if there is nothing useful, there are general ways to implement algorithms. If doing something yourself, take platform specifics into account if performance matters.

LyndsySimon 10y ago
In my experience, finding the right search terms is 80% of the battle. Knowing the phrase "Dijkstra's Algorithm" is a big leg up here, and would put me only one or two degrees of separation away from the correct answer. If I didn't know that term, then I'd search "shortest path directed graph". That leads to a Wikipedia article with links to a variety of algorithms.