Dijkstra finding shortest path satisfying given constraints

Question

The question is originated from Hackerrank.

Suppose there are 1 to N stores in a city which are connected by bidirectional roads associated with traveling times. Each store sells some types of fishes (0 <= type_of_fish_store_i < K), in total K types of fishes are selling in the city. A cat starts at store 1 and traveling along some path puchases fishes at each store on the path.

Calculate minimum time that satisfies the constraints

• the cat has to end at a specified store X
• the cat has to end with specified types of fishes in the basket

Note: a store including the final destination can be visited more than once

Shop and fish types selling at that shop ({shop:fish_type}):

{1: {1}, 2: {2}, 3: {3}, 4: {4}, 5: {5}}

Adjacency matrix with cells filled with time cost (referring to cost_matrix):

[[0, 10, 10, 0, 0],
 [10, 0, 0, 10, 0],
 [10, 0, 0, 0, 10],
 [0, 10, 0, 0, 10], 
 [0, 0, 10, 10, 0]]

Approach I've implemented:

def dijkstra(cost_matrix, start, wanted, end):
    """

    :param cost_matrix: adjacency matrix filled with time costs
    :param start: the store where the cat starts at
    :param wanted: types of fishes the cat wants at the end of journey
    :param end: the store where the cat ends at
    :return: 
    """
    fish_basket = shop_and_fish[start]
    accum = 0
    h =[]
    visited = [start]

    while not (wanted.issubset(fish_basket) and start == end):
        for i, dist in enumerate(cost_matrix[start - 1]):
            if dist > 0:
                    heapq.heappush(h, [ accum + dist, i + 1, fish_basket | shop_and_fish[i + 1], visited + [i + 1]])
        # print("heap: ", h)
        accum, start, fish_basket, visited = heapq.heappop(h)
    print("Total time: ", accum, ", End store:", start, ", Fish types collected: ", fish_basket, ", Path: ", visited)
    return accum

Execute:

dijkstra(cost_matrix, 1, {1,2,3,4,5}, 5)
# this is saying the final accepted state is the cat 
# at 5th store with {1,2,3,4,5} types of fishes in hand

Returns

50
# Total time:  50 , End store: 5 , Fish types collected:  {1, 2, 3, 4, 5} , Path:  [1, 2, 4, 5, 3, 5]

Problem

Efficiency. Expanding unnecessary nodes such as [1,2,1,2,1,2], in some other cases [1,2,3,4,3,2,1,2,3,4..], maybe some other unforeseen patterns. Any thoughts on how to eliminate them? I've tried palindrome, but it seems to add a lot of complexity as it examines every path and every subpath of that path. Moreover, if you've identified any other improvements, feel free to add to answer.

Answer 1

This is an interesting problem. You hacked Dijsktra's algorithm to make it solve the problem, but this hack has a cost. In Dijkstra's classical algorithm:

• you stop once all nodes have been visited;
• you start an iteration with the best (shortest) candidate path.

In your version:

• you stop once you reach your destination and you have a full basket of fishes;
• same start for iterations.

Basically, you walk until your basket is full and then you rush to the end store. The BFS selection ensure you that you get the effective shortest path (good point: your algorithm is correct).

Of course, without the Dijkstra's stop condition, your algorithm is not O(n lg n) anymore.

Consider the following graph for instance:

A -- B --...-- C

The cost_matrix is:

cost_matrix =  [[0, 1, 0],
                [1, 0, 999],
                [0, 999, 0]]

If you look for a path from 1 to 3, your function will play ping-pong between 1 and 2 until the distance reaches 999 and then consider 3.

A bit of theory now. Take the following instance of your problem: every store (node) has only one type of fish, and two stores do not have the same type of fish. You want a basket filled with all existing types of fish. That means: you have to visit each store at least once. This is a variation of the Travelling Salesman problem because you are allowed to visit every store mutliple times, but the complexity is the same (see https://math.stackexchange.com/questions/1269983/traveling-salesman-problem-why-visit-each-city-only-once and https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity).

Hence, I think you won't find any easy answer. It seems to me that your best choice, if you want to improve efficiency, is to "branch and bound".