I was wondering for question 1, do we assume the graph has undirected or directed edges?
In the 1st question, you have to figure out yourself what graph you can use to represent correctly information given to you. So, it is up to your decision whether you will be using a directed or undirected graph in Q1.
Is the 1st question from the assignment really easy, or may be I'm missing something?
Yes, this is a rather easy question. You just have to add a few lines to one of the algorithms considered in class. However, you have to provide also a detailed complexity analysis of the resulting algorithm. I would say that all questions in this assignment are not difficult.
In question 2 you ask us to find a DP algorithm that needs to find the "number of shortest path", by definition shortest would mean that there is only one path that is the best (or shortest) so if you ask us to find the number of shortest that would translate as that we are required to find one path that is the shortest and all others that are equal to it. Is that correct? It just does not make sense to me to have many shortest paths. Let me know if I am on the right track.
If you study carefully the graph provided for Q1 in the assignment, then you can notice easily that there are several shortests paths between the vertices S and F. For example, S-A-C-D-F has the total weight 6 and is the shortest path between S and F, but there are other shortests paths as well: S-A-C-E-F, S-B-C-D-F, S-C-E-F, and so on. All of them have the same total weight 6. In Q2, you are asked to find the number of shortest paths between any two nodes V and W in a directed graph, where weights can be positive or negative. For the example above, the answer for vertices S and F would be 6 since there are 6 distinct shortests paths from S to F: 3 shortest paths from S to C times 2 shortest paths from C to F.
How can we reduce this problem to one of the problems solved in class?
Yes, in Q3 of the assignment, you have to describe clearly which graph you use and why it is convenient.
For assignment 3 question 2, do you want us to describe the steps of developing the algorithm that will solve this problem like we did in the previous assignment?
Yes, please follow the outline from the 2nd assignment. Also, I mentioned all the steps in class, when I explained the methodology of designing DP algorithms.
I am just wondering for part 2 which asks us to count the number of shortest paths. Are we only considering shortest paths with minimal edges, or just simply all shortest paths with minimal cost?
We are looking for shortests paths in terms of minimal total cost. Develop an a DP algorithm that will count the number of all such shortest paths.
For question 2 we are writing an algorithm for the length of a shortest path of a directed graph. Part 5 of the questions asks us to trace our algorithm using the graph from part 1. This graph however is undirected. Should we be assuming the direction of all edges is just towards F (and away from S)?
Yes, assume that all adges are going in the direction away from S and towards F.