Я думаю, что это действительно зависит от желаемого результата. Одна возможность:
digraph G {
graph [ splines = false ]
a -> b [ label = "foo" ];
a -> b [ label = "bar" ];
}
Если сплайны не используются, рисуются ребра с прямыми отрезками, поэтому дублированные ребра не будут различаться визуально.
Каким будет один край в вашем идеальном выводе, поскольку для него должно быть два разных ярлыка?