I have a graph with a int label and int cost associated with each edge. The graph is represented as an adjacency list. Given an int array, find a path through the graph that traces the values of the ints in the array while at the same time minimizing the cost acrued during the trace. That is, the first edge in the path should have a label that matches the array[0], and the second edge in the path should have a label that matches array[1], etc…. Any node may be the start. Parallel edges are allowed. An edge may be traversed more than once. Specifically: what is the fastest algorithm to both trace the given path and minimize the cost of the path? How should the labels and costs be represented in the adjacency list? Right now, I have basically a BFS, where the potential paths are kept in a priority list sorted by the total cost. Only edges that have labels that match the current index of the array (ie, the current path-label) are considered in the BFS. However, this seems rather slow as I’m optimizing for speed?
