Conditional Shortest Path Through Weighted Cyclic Directed Graph

Question

Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge represents the destination.

My graph has negative cycles, for example [A-red, B-red, C-blu, X-grn, D-blu, A-red] has a cost of -1, comprised of edge costs [1, 1, -1, -3, 1].

I want to find the shortest path between arbitrary {source, destination} vertices subject to the following conditions:

1. Each vertex may only be visited once.
2. The count of vertexes visited along the path must be <= m
3. The count of categories visited along the path must be <= n

So, for example, assuming a function shortest_path(source, dest, m, n) then:

shortest_path(('A','red'), ('D','ylw'), 100, 100) would return [A-red, B-red, C-blu, X-grn, D-ylw] which has a cost of -2. This path visits 4 vertex categories [red, blu, grn, ylw].

shortest_path(('A','red'), ('D','ylw'), 100, 3) would return [A-red, B-red, C-blu, D-ylw] for a cost of 3. This path visits 3 vertex categories [red, blu, ylw].

Any suggestions here? I believe Dijkstra's algorithm and Bellman-Ford are out here as my graph contains negative cycles. So I think i need a brute force search of edges, integrating the stopping conditions mentioned above.

Python code for initializing my graph is here:

import networkx as nx

class Vertex(object):
    def __init__(self, name, category):
        self.name = name
        self.category = category
    def __hash__(self):
        return hash((self.name, self.category))
    def __eq__(self, other):
        if isinstance(other, Vertex):
            return other.name == self.name and other.category == self.category
    def __str__(self):
        return '{}-{}'.format(self.name, self.category)
    def __repr__(self):
        return str(self)

d = {
    Vertex('A','red') : {Vertex('B','red') : {'weight':1}},
    Vertex('B','red') : {Vertex('C','blu') : {'weight':1}},
    Vertex('C','blu') : {Vertex('D','ylw') : {'weight':1}, Vertex('X','grn') : {'weight':-1}},
    Vertex('D','ylw') : {Vertex('A','red') : {'weight':1}},
    Vertex('X','grn') : {Vertex('D','ylw') : {'weight':-3}},
}
G = nx.DiGraph(d)

pos = nx.circular_layout(G)
nx.draw_networkx(G,pos, arrows=True, with_labels=True)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos, edge_labels=labels);

Update Here is my current traversal algorithm, its essentially a DFS but I record both the parent of each vertex I examine, and the cost of traversing from the parent to the vertex. This allows me to reconstruct a path and compute a total cost for the path. However, I'm not sure its a great solution. My aim is to get the algorithm working well then port to cython for performance (my real graph is huge).

#DFS
def calcd(parents, distances):
    d = 0
    for v in parents[1:]:
        d+=distances[v]
    return d

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path

def dfs(graph, source, target):
    visited = set()
    stack = list()
    parent = {}
    distance = {}

    stack.append(source)

    while stack:
        u = stack.pop()
        uob = graph[u] #edges outbound from u

        for v, eparams in uob.items():
            parent[v] = u
            distance[v] = eparams['weight']

            if v == target:
                path = backtrace(parent, source, target)
                print('Reached Target via {}'.format(path))
                print('calcd', calcd(path, distance))

            if v not in visited:
                visited.add(v)
                stack.append(v)

source, target = Vertex('A','red'), Vertex('D','ylw')
dfs(G, source, target)

This prints:

Reached Target via [A-red, B-red, C-blu, D-ylw] calcd 3 
Reached Target via [A-red, B-red, C-blu, X-grn, D-ylw] calcd -2

Answer 1

The problem is NP-hard, even when you ignore the constraints about categories. See https://cstheory.stackexchange.com/q/17462/5038 for a simple proof based on a reduction from the longest path problem (or from the Hamiltonian path problem). Therefore, you should not expect any efficient algorithm.

There are algorithms whose running time is polynomial in the size of the graph but exponential in $m$ (the length of the path). See https://en.wikipedia.org/wiki/Longest_path_problem#Parameterized_complexity.

The categories don't increase the complexity of the problem by more than a constant factor, since there are only 4 categories. For instance, if the path is required to use at most 3 different categories, you can enumerate all ${4 \choose 3}$ subsets of 3 categories, and for each, construct a smaller graph that contains only the vertices in that subset and then solve the problem on that graph without the restriction on the number of categories. So for an algorithm design perspective, I suggest you first solve the problem while ignoring the categories. It will then be straightforward to extend your solution to deal with the categories.