[snip]
OK! Well, the problem come from telecom. In telecom, network element can be viewed as vertex. network element is a device that can be plug in "lines"(optic, ethernet or anything can transmit data). These "lines" have a character: composited by 2 transmition medium. So if 2 network element was connected by a line, you can send data from source to target or from target to source. But notice that 2 direction has independent band width. For example, a 5M line connect vertex A & B, you can establish a connection between A & B. This connection have 2 type: uni or bi. A bi-direction connection means you can send data from A to B AND B to A at max width 5M. A uni-direction connection means you can ONLY send data from A to B OR B to A(depend on connection's source & destination), the line between A & B has been used only one capacity. That is, only one transmition medium in this line has been used. So, a line can contain 2 uni connection(one is A to B, another is B to A) or 1 bi connection.
This problem requires dijkstra algorithm accept one more parameter: Path's Direction.
At this point you still have not stated the problem! Is it something like this? : Given a graph G=(V,E,T,C), V is a set of vertices; E is the set of edges. Each edge has two integer properties: edge type T: E -> {UNI, BI} and edge capacity C: E -> INT. Given two vertices: "s" (start vertex) and "f" (finish vertex) and a path_type (uni or bi). Your task is to find a shortest path P from start vertex "s" to finish vertex "f" (the weight map is C ??) such that all edges of this path are of the corresponding type (uni or bi), i.e., for each edge e \in P, T(e) == path_type. It is quite strange to be true. First of all because we are trying to find a path with the smallest bandwidth. Something should be added to this formulation. Does your graph have cycles? Please, provide a small example (a graph with several vertices and edges).
BGL have not this. This problem requires graph can not be a directed-graph. Because a bi connection can not go through different "line". This problem requires graph has it runtime type, that is, when routing uni-connection, graph should be a directed-graph. when routing bi-connection, graph should be a undirected-graph. If we need to avoid re-create graph when connection direction type changes, we must...customize BGL.
The best solution I can figure out is reduce the problem to a undirect-graph but its edge has complex properties. These properties value affect algorithm behavior. The problem is: how to do this??
re-creation graph is easy. But this creation cost is high: based on a graph, routing 100,000 connections need to create graph 100,000 times in worst case.
Dmitry