Showing posts with label Dijkstra. Show all posts
Showing posts with label Dijkstra. Show all posts

Saturday, November 12, 2011

Greedy algorithm, Google Map vs Map Quest, WiFi vs 3G

Comment 1:

Are there other algorithms to find the shortest path that use recursion or dynamic programming?

Follow-up:

Yes there is one called Floyd-Warshall algorithm that uses dynamic programming to find all-pairs
shortest paths. This algorithm can also handle graphs with negative link weights.

Comment 2:

What happens in the shortest path greedy algorithm (i.e., Dijkstra) when two distances surrounding the node are equal?

Follow-up:

Good observation. We will usually just “randomly” choose one to break the tie.

Comment 3:

Any technical and systematic ways to calculate the time-complexity of an algorithm?

Follow-up:

Yes sure. For more complicated situation, we usually end up having a bunch of summations of series in the counting of number of key steps. Then, we will need to use some mathematical tools to obtain closed-form expressions. These are computer science topics, though.

Comment 5:

If 3G and Wi-Fi on my smartphone are similar things, why do I notice a significant difference between the speed of loading the same page on 3G and Wi-Fi?

Follow-up:

3G and Wi-Fi are similar in that they are both wireless communication technologies. But the similarity ends there. The wireless communication mechanisms used are highly different in many aspects. For example, 3G is based on cellular communication which is designed for longer range and thus, speed is lower (as electromagnetic signals deteriorate significantly over a distance). Wi-Fi is of a much shorter range and can therefore afford to provide a higher speed. There are many other technical differences, which are topics of a wireless communication and networking course.

Comment 6:

The “shortest path algorithm” can be demo-ed on 9 slides with animation instead of using just one slide. It is a bit too small.

Follow-up:

Thanks for the comment! You are right! Will improve this. Sorry for the inconvenience.

Comment 7:

How come MapQuest/Google-Map is so fast on a map that has billions of nodes?

Follow-up:

One trick is that MapQuest/Google-Map generally does not do the computations “on-demand”, i.e., they pre-computed many routes which are then stored in the database. When someone posts a query, majority of the routes are pulled out from the database.

Comment 9:


How to resolve the conflict when there is negative weight in the graph when using Dijkstra’s
algorithm?

Follow-up:

Dijkstra’s algorithm fails when there is negative weight in the graph. We will need to use a different technique, e.g., the Bellman-Ford algorithm. See also Comment 1 above.

Comment 10:

You have mentioned that researchers in the field of computer try to giving everything an unique ID (a unique IP address), for example, a microwave oven. However, I don’t really understand why we are going to do so. What are the purposes? If that applies widely, will there be any privacy problems?

Follow-up:

Yes sure I believe there will be significant privacy problems! Maybe you can consider using this as your survey topic?

Comment 11:

How do we obtain (e + n log n) for Dijkstra’s algorithm?

Follow-up:

A rough sketch as follows: We need to examine all the links (during the updating of the estimated distances labelled on the nodes) so that is why we have the e term. We need to sort the nodes in an increasing order of estimated distances and that is why we have the n log n term.

Comment 12:

Why greedy approach usually results in a fast algorithm?

Follow-up:

This is because as we make a greedy choice in each step, we reduce the problem size by 1. Thus, after making n greedy choices (i.e., n steps), we will finish the problem. Consequently, we usually end up having an algorithm that takes O(n) time, together with the time needed in some pre-processing (e.g., sorting, which takes another n log n time).

Comment 13:

Knapsack problem. It can e applied to daily life. Is it similar to linear programming taught in Maths at cert level?

Follow-up:

Yes it is similar. Wait until Tutorial 3 to find out more details.

Comment 14:

Dynamic programming is a bit difficult to understand. Also the DNA sequence example.

Follow-up:

The theme of Tutorial 3 is about dynamic programming. Hope you would feel better after going
through this tutorial cycle. The DNA sequence example is interesting and I think you can understand at least 70% of it by studying the Web page mentioned in class.

Comment 15:

I am a bit confused of the graph that represent the different representation of running time that results in different value.

Follow-up:

I think you are talking about the “estimated distances” labelled on the nodes in the example graph for showing how Dijkstra’s algorithm works. Those values are NOT running time (of an algorithm). Those are used for representing, for example, the time it takes to travel from one place to another geographically (when we use the graph to represent a map).

Comment 16:


Why “99” is used to represent the information that has not been processed?

Follow-up:

Yes in computer programming we usually use such tricks to ease processing.

Comment 18:

Google-Maps are more developed than MapQuest these days. For example, it can alert that friends are located close by to you.

Follow-up:

Thanks!

Comment 21:

I am not quite clear about how two determinant factors will affect the efficiency of greedy approach.

Follow-up:

The main factors are the “greedy choices”. If you pick the right greedy choice at each step, the
algorithm would end up giving “optimal” result. In terms of speed, please refer to Comment 12 above.

Sunday, July 24, 2011

Communication networks design using graph problem

Problem:

In addition to finding shortest paths, sometimes we are also interested in finding the set of links connecting all the nodes with the minimum cost. A real life application of this idea is in the design of communication networks. Here, the nodes of the graph represent sites and the links represent the communication connections between sites. The cost of each connection could be the communication delay. Using the following graph as an example, can you design an algorithm similar to the Dijkstra’s algorithm in solving this problem?

Follow-Up:

To solve this problem using a greedy method, we can use the Kruskal’s algorithm, outlined below.
  1. Sort all links in ascending order of costs
  2. Start with an empty set of links, so that all nodes are disconnected (isolated)
  3. Add the lowest cost link to the set to connect a disconnected node without creating a cycle; this link is not to be considered again
  4. Repeat Step (3) until the set has n - 1 links

Further Inquiry:

(a) What is the estimated running time of the above algorithm?
(b) If there are links with negative costs, would this greedy method still work?

Thursday, July 21, 2011

Computations in Google Map

Comment:

Why Google cannot store the complete map easily? For instance, for 1000 nodes, we need to store just around 500 × 999 units of data.

Follow-up:

While the analysis for 1000 nodes is correct, when you scale it up to 1 million nodes, the data storage becomes very big. Indeed, the file size of the street map for the U.S.A. is around 9GB (for details, please visit: www.esri.com). Thus, for the entire world with all the details (e.g., restaurants, shops, timing data, etc.), the data size would be even larger. Of course, Google still can “easily” handle all these. But to run an algorithm (e.g., Dijkstra) over such a large piece of data is still quite daunting. That is why we really have to use the “pre-compute-then-table-lookup” approach as far as we can.

Comment:

What kind of programming language is used for implementing MapQuest and Google Map?

Follow-up:

For high-performance applications, I strongly believe that their engineers are still relying on the C language. However, for other system components such as user interface, Web, etc., they use a variety of other tools (e.g., Java, Perl, Python, etc.).

Sunday, July 17, 2011

Dijkstra's shortest path, Computation

Comment 1:

How to derive the Dijkstra’s shortest path algorithm’s estimated running time?

Follow-up:

As an approximation, we note that each link needs to be visited at once. In the worst case, we can have on the order of (n x n) links, where n is the number of nodes in the graph. Thus, the estimated running time is approximately (n x n) steps.

Comment 3:

Maybe it is true that if we put in more computing/storage resources, we can solve just about any problem.

Follow-up:

If you attended Tutorial 3, you should have learned that there are really difficult problems, in the sense that you will need unreasonably large amount of storage (e.g., every atom in the universe) and computing power to solve. Furthermore, in Problem 3 of Tutorial 3, you will see that there are problems that are simply unsolvable.

Dijkstra's shortest path problem

Problem:

We learn about the Dijkstra’s shortest path algorithm in class. Try to apply it to the following graph.



What is the shortest path between s and b?

Follow-Up:

Using Dijkstra and starting from s, the shortest path found is s-a-b. Yet we can easily see that the shortest path should be s-a-c-b. Thus, we can see that greedy method does not always work. Here, Dijkstra is defeated by the existence of links with negative costs.

However, as some of you discovered during the tutorial, the correct shortest path can be found by starting the Dijkstra work from the destination, i.e., b. Please try this yourself.

Indeed, in real-life usage (e.g., in software systems such as MapQuest), a bi-directional approach is used, i.e., the Dijkstra work is done concurrently from both the starting point and the destination. Conflicts are resolved on the way to construct the final shortest path.

Further Inquiry:

Consider that the link costs are multiplied together (e.g., when the links are associated with probabilities) in a path, would Dijkstra still work?