Dyanmic Shortest Path

Question

Your friends are planning an expedition to a small town deep in the Canadian north next winter break. They’ve researched all the travel options and have drawn up a directed graph whose nodes represent intermediat destinations and edges represent the reoads betweeen them. In the course of this, they’ve also learned that extreme weather causes roads in this part of the world to become quite slow in the winter and may cause large travel delays. They’ve found an excellent travel Web site that can accurately predict how fast they’ll be able to travel along the roads; however, the speed of travel depends on the time of the year. More precisely, the Web site answers queries of the following form: given an edge e = (u, v) connecting two sites u and v, and given a proposed starting time t from location u, the site will return a value fe(t), the predicted arrival time at v. The web site guarantees that 1 fe(t) > t for every edge e and every time t (you can’t travel backward in time), and that fe(t) is a monotone increasing function of t (that is, you do not arrive earlier by starting later). Other than that, the functions fe may be arbitrary. For example, in areas where the travel time does not vary with the season, we would have fe(t) = t + e, wheree is the time needed to travel from the beginning to the end of the edge e. Your friends want to use the Web site to determine the fastest way to travel through the directed graph from their starting point to their intended destination. (You should assume that they start at time 0 and that all predictions made by the Web site are completely correct.) Give a polynomial-time algorithm to do this, where we treat a single query to the Web site (based on a specific edge e and a time t) as taking a single computational step.

    def updatepath(node):
        randomvalue = random.randint(0,3)
        print(node,"to other node:",randomvalue)
        for i in range(0,n):
            distance[node][i] = distance[node][i] + randomvalue

    def minDistance(dist,flag_array,n):
        min_value = math.inf
        for i in range(0,n):
            if dist[i] < min_value and flag_array[i] == False:
                min_value = dist[i]
                min_index = i
        return min_index

    def shortest_path(graph, src,n):
        dist = [math.inf] * n
        flag_array = [False] * n
        dist[src] = 0

        for cout in range(n):
            #find the node index that have min cost
            u = minDistance(dist,flag_array,n)
            flag_array[u] = True
            updatepath(u)
            for i in range(n):
                if graph[u][i] > 0 and flag_array[i]==False and dist[i] > dist[u] + graph[u][i]:
                    dist[i] = dist[u] + graph[u][i]
                    path[i] = u
        return dist

I applied Dijkstra algorithm but it is not correct ? What would i change in my algorithm to work it for dynamic changing edge.

Answer 1

Well, Key points are that function is monotonically increasing. There is an algorithm which exploits this property and it is called A*.

Accumulated cost: Your prof wants you to use two distances one is accumulated cost(this is simple the cost from previous added to the cost/time needed to move to the next node).

Heuristic cost: This is some predicted cost.

Disjkstra approach would not work because you are working with heuristic cost/predicted and accumulated cost.

Monotonically increasing means h(A) <= h(A) + f(A..B).It simply says that if you move from node A to node B then the cost should not be less than the previous node (in this case A) and this is heuristic + accumulated. If this property holds then the first path which A* chooses is always the path to goal and it never needs to backtrack.

Note: The power of this algorithm is totally base on how you predict value.

If you underestimate the value that will be corrected with accumulated value but if you overestimate the value it will chose wrong path.

Algorithm:

Create  a Min Priority queue.
insert initial city in q.

while(!pq.isEmpty() && !Goalfound) Node min = pq.delMin() //this should return you a cities to which your distance(heuristic+accumulated is minial). put all succesors of min in pq // all cities which you can reach, you can better make a list of visited cities s that queue will be efficient by not placing same element twice. Keep doing this and at the end you will either reach goal or your queue will be empty

Extra

Here i implemented a 8-puzzle-solve using A*, it can give you an idea about how costs are defined and ho it works.

`

private void solve(MinPQ<Node> pq, HashSet<Node> closedList) {
        while(!(pq.min().getBoad().isGoal(pq.min().getBoad()))){
            Node e = pq.delMin();
            closedList.add(e);
            for(Board boards: e.getBoad().neighbors()){
                Node nextNode = new Node(boards,e,e.getMoves()+1);
                if(!equalToPreviousNode(nextNode,e.getPreviousNode()))
                      pq.insert(nextNode);
               }
            }
        Node collection = pq.delMin();
            while(!(collection.getPreviousNode() == null)){
                this.getB().add(collection.getBoad());
                collection =collection.getPreviousNode();
        }
            this.getB().add(collection.getBoad());
            System.out.println(pq.size());
    }

A link to full code is here.