Monday, January 24, 2011

Finding short cuts

Professor Chen discussed the graph theory today, including some fundamental concepts and simple applications. What I felt most interested was the Dijkstra's algorithm.Dijkstra's algorithm is also called the greedy algorithm that I think it is easier to remember. It is greedy because "every decision it makes is the one with the most obvious immediate advantage".

Here is a demonstration on how the algorithm works.

Dijkstra's algorithm runtime

Porfessor Chen didn't go further into the details about the algorithm.We didn't go further into the details of the algorithm. But I felt that finding a short cut should be a good application of graph theory; not merely in the field of computer science, but also in social science, even in our daily life.

An obvious example for this algorithm is how to find the shortest way to build a highway between several cities. Or, if I want to make $73, what and how many bills and coins I shall choose to make sure that I take the largest possible bill or coin. Another application occurs to me is finding the shortest path in the network of links of searching results to get the most helpful information, or how to make up the shortest and most informative reading list for literature review among countless references. I am greedy too :)

No comments: