Dijkstra finding shortest path satisfying given constraints
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".