If you have mixed edges you don't use BFS you use Dijkstra's algorithm preferably with a heap and the example you said is still not a problem. The short path made of many edges would be pulled out of heap first ensuring first time visit is still the shortest. If you run actual BFS on non uniform edges, for something like a->b a->c b->d c->d d->e it won't ecesseryn even produce the shortest path at all, only way i can imagine it working is to drop the requirement of not visiting single node twice for it to produce shortest path. At that point it's not BFS at all, and not only you would have to visit whole graph you would have to visit whole graph multiple times, worst case expontially if you have something like braching chain of paths.