Introduction
This answer is in two parts.
The first is an analysis of the problem mixed with a sketch of the
algorithm to solve it. As it is my first version, it is detailed, but
results in an algorithm that is a bit more complex than needed.
It is followed by a pseudo-code version of the algorithm, written sometime later, as the algorithm was clearer. This pseudo-code is more
direct, and somewhat simpler, but probably easier to understand after
reading the first part.
In retrospect, the more important ideas are:
to see that the maximum distance of a node to the new node C, as a
function of the length of $(A,C)$, is given by the superposition of
roof shaped (inverted V) curves, characterized by their top,
associated to nodes of the graph.
to see that irrelevant curves can be eliminated efficiently by a
scan in monotonic order of abscissa of tops (with minimum backtrack).
then minimal points can be enumerated simply by intersecting the remaining
curves two by two, again in monotonic order of abscissa of tops.
Sketch of an algorithm
NOTE: I changed the initial presentation of the question to get a more
standard view of graphs, by considering that the edge $(A,B)$ is
replaced by a new node $C$ and two edges $(A,C)$ and $(C,B)$ with the
same total length as $(A,B)$.
Let $(A,B)$ be the distinguished edge, and let $l$ be its length. Let
$e$ and $n$ be respectively the number of edges and the number of
nodes in the graph.
First you remove the edge $(A,B)$. Then, for every node $U$ of the
graph, you compute the distance $\alpha(U)$ between $A$ and $U$, and
the distance $\beta(U)$ between $B$ and $U$. This can be done with
Dijkstra's shortest path algorithm, in time $O(e+n\log n)$.
Then you add a new node $C$ with an edge $(A,C)$ and an edge $(C,B)$,
of length respectively $a$ and $b$, such that $a+b=l$. The
length $a$ is not known, and is to be found so as to minimize the
distance of the most remote node to node $C$. The distance of $C$ to
$A$ or $B$ may be 0.
The difficulty of the problem is that the node most distant from $C$
via $A$ may be close to $C$ via $B$, and thus does not matter. Also, a
node closer to $C$ via $A$ than via $B$ may inverse that situation as
$C$ moves between $A$ and $B$, i.e. as $a$ varies in $[0,l]$.
We consider three sets of nodes in the graph, forming a partition of
all nodes:
the set $N_A$ of nodes that are always closer to $C$ via $A$
independently of the value of $a$:
$N_A=\{U|\alpha(U)+l\leq\beta(U)\}$
the set $N_B$ of nodes that are always closer to $C$ via $B$ independently
of the value of $a$:
$N_B=\{U|\beta(U)+l\leq\alpha(U)\}$
and $N_{AB}$ the set of nodes that can be closer to $C$ via $A$ or
via $B$, depending on the value of $a$, actually closer via $A$ for
smaller values of $a$, and closer via $B$ for larger values of $a$ in $[0,l]$:
$N_{AB}=\{U\mid\alpha(U)+l>\beta(U) \wedge \beta(U)+l>\alpha(U)\}$
Let $U_A$ the node in $N_A$ most remote from $A$, and $U_B$ the node
in $N_B$ most remote from $B$.
No other node in $N_A\cup N_B$ is ever more distant from $C$ than the
more distant of these two nodes, whatever the distance $a$ of $(A,C)$.
Hence all other nodes in $N_A\cup N_B$ can be discarded for the
computation of the optimal value of $a$.
Note that it may happen that $N_A$, or $N_B$, or both, are empty. In
which case, the corresponding nodes $U_A$ and/or $U_B$ do not exist.
We will build a distance curve on a plane with coordinate $(x,y)$, which will
ultimately represent the longest distance $y$ of a node from $C$ as a
function of the distance $x=a$ of $C$ from $A$. Hence $x=a\in[0,l]$
This distance curve is actually a zig-zag composed of segments angled $\pm
45^\circ$. Once it is built, the point minimizing the longest distance
is to be found in the minimal points of the curve. There may be
several such points. All these points have to be computed, and then
compared.
We describe below how to compute them.
Actually, we consider a collection of simpler distance curves, with only one or
two segments in the interval $[0,l]$, such that the longest distance of
a node from $C$ is always on or above the curve. The final curve is
obtained by taking for every value of $x$ the maximum value of $y$
given by one of the distance curves. This can be done formally by computing the
intersection of the segments in an ordered fashion.
First we have (at most) two distance curves composed of only one segment. These
are the curves corresponding to the distance of $U_A$ and $U_B$ to
$C$. The first is upward at a $45^\circ$ angle, and the second is
downward at a $45^\circ$ angle.
Assuming no other node is ever more distant from $C$, the optimal
value of $a$ is the abcissa of their intersection. At that abscissa,
that value for $a$, the nodes $U_A$ and $U_B$ are at the same distance
from $C$. Hence the distance is minimum when $a$ satisfies the
equation $\alpha(U_A)+a=\beta(U_B)+b$. Since $a+b=l$, this gives
$\alpha(U_A)+a=\beta(U_B)+l-a$, and finally
$a=(\beta(U_B)-\alpha(U_A)+l)/2$. This corresponds to a distance
$y=(\alpha(U_A)+\beta(U_B)+l)/2$ of both nodes to $C$.
Together, the two curves give a V shaped curve, with a minimum at the
point just computed.
But we also have to account for all the nodes in $N_{AB}$. The
distance of a node $U\in N_{AB}$ to $C$ first increases with $x$ while
the shortest path goes through $A$, them it decreases with $x$ when
the shortest path goes through $B$. Hence, the corresponding distance curve is
formed of two segments, roof shaped, with a maximum at an abscissa
such that the distance to $C$ is the same through $A$ or through $B$.
This gives the equation $\alpha(U)+a=\beta(U)+b$. Resolving it as
above, we get $x=a=(\beta(U)-\alpha(U)+l)/2$, and
$y=\alpha(U)+\beta(U)+l)/2$. We note $T_U$ (for Top of $U$) the point
with these coordinate. The top $T_U$ characterizes the roof shaped distance
curve for node $U$ since the slope of both side is $\pm 45^\circ$.
Now all the difficulty of the problem is that several nodes $U\in
N_{AB}$ may be such that $T_U$ is above our first V-shaped curve,
which will lead to the final zig-zag line.
But, we first can eliminate all nodes $U\in N_{AB}$ such that $T_U$ is
below the V-shaped distance curve, as they will not ever contribute to the
longest distance. This is easily done and is skipped here for clarity.
Then we want also to eliminates all nodes $U\in N_{AB}$ such that
their roof-shaped curve is always below the curve of another node
$V\in N_{AB}$. This is determined by the position of their tops, and
we say that $T_V$ dominates $T_U$, or that $V$ dominates $U$. Actually
$T_V$ and $T_U$ are in a domination relation iff the absolute value
of the abcissa difference is less than the absolute value of the
ordinate difference. The dominating node/top is the one with the
highest ordinate.
For this purpose, we first sort all tops of the remanining nodes of
$N_{AB}$ in ascending order of increasing abscissa. This is done in
time $O(n\log n)$.
Then we remark that if top $T_U$ dominate a non adjacent top $T_V$,
then any intermediary top $T_W$ dominate $T_V$, or is dominated by
$T_U$, or both. Hence, to eliminate all nodes/tops that are dominated,
on can simply proceed from left to right (by increasing abscissa),
comparing only adjacent nodes, and removing any that is dominated. If
the node on the right is dominated, it is removed and the node on the
left is compared again to the next right. If the node on the left is
dominated, it is removed and the node on the right is then compared
with the previous one on its left. If none dominates the other, then the node on left
is kept, and the node on right
is then compared with the next right. This is repeated until the
rightmost node/top has been thus processed, in time $O(n)$.
Whatever nodes have been kept do contribute to the final curve, in
left to right order of their tops, with the line for $U_A$ at the left
and the line for $U_B$ at the right, if they exist. The minima are
easy to compute by considering the intersections of the contributing
curves from left to right, in time $O(n)$.
Finally, the abcissa for the smallest distance of all nodes to $C$ may be
found by a linear scan of all minima for the lowest ones. They may
actually be several such abscissa, i.e. values for the length $a$ of
edge $(A,C)$.
If the distances have to be integers, the abscissa of the minima can be
rounded up or down.
The time complexity of the algorithm is: $O(e+n\log n)$.
With thanks to user3153970 who remarked that my initial solution was
not quite correct.
Pseudo-code version
The procedure described in the analysis of the problem is modified or
improved in some ways.
the length l is changed to d to avoid confusion with the number 1.
for simplification, the V curve is replaced by two tops of roof curves placed on
both end of the interval [0,d].
the sets $N_A$ and $N_B$ need not be created. Only $d_A$ and $d_B$
are needed, briefly, to crate the two extra tops.
the set $N_AB$ is not created either, only the corresponding set
(actually a multiset, or bag, that may be implemented as a list) of tops, as two distinct nodes may
produce the same top, if at the same distance of A and B.
(bugs are provided free of charge)
d := distance (A,B)
none := -1 % programming trick - none is for distances to be ignored %
Remove the edge (A,B) from the graph.
Using Dijkstra's shortest path algorithm, for every node $U$ compute its shortest
distances α(U) and β(U) to respectively A and B.
d_A := none
d_B := none
% We use lists of pairs, representing the [x,y] coordinate of points, where the %
% abcissa x stands for the choice of length (A,C), and the ordinate y stands is the %
% distance of some node to C. %
% The call first(L) returns a pointer to the first pair of list L. %
% Given a pointer t to a pair, t.x and t.y give the two components of the pair, %
% and the functions prev and next return a pointer to the previous or the next pair, or %
% NIL if it does not exist. The call add([a, b], L) adds the pair [a, b] to the list L. %
% The call remove(t) removes the element pointed by t from its list. %
For every node U do
T := [] % T is the list of tops of curves for individual nodes %
if α(U)+d ≤ β(U) then d_A := max(d_A, α(U))
elsif β(U)+d ≤ α(U) then d_B := max(d_B, β(U))
else add( [(β(U)-α(U)+d)/2, (β(U)+α(U)+d)/2], T)
% Instead of V curve, create dummy tops at ends of [0,d] interval %
if d_A ≠none then add( [d, d_A+d], T)
if d_B ≠none then add( [0, d_B+d], T)
Sort T in increasng order of abscissa
% Remove from T all tops that are dominated by another top %
t1 := first(T)
t2 := next(t1)
Repeat
if abs(t1.x-t2.x) ≤abs(t1.y-t2.y)
then % one top dominates the other %
if t1.y≥t2.y
then % t1 dominates %
remove(t2)
t2 := next(t1)
if t2=NIL then exit loop
else % t2 dominates %
remove(t1)
t1 := pred(t2)
if t1=NIL then
t1 := t2;
t2 := next(t1)
if t2=NIL then exit loop
else % neither top dominate the other %
t1 := t2
t2 := next(t1)
if t2=NIL then exit loop
% Compute all local minima %
M := [] % M is the list of minima, where roof shaped curves intersect, %
% or intersect the boundaries of the interval [0.d]. %
t2 := first(T);
if t2.x≠0 then add( [0, t2.y-t2.x], M)
repeat
t1 := t2
t2 := next(t1)
if t2=NIL then exit loop
add( [(t1.y-t2.y+t1.x+t2.x)/2, (t1.y+t2.y+t1.x-t2.x)/2], M)
if t2.x≠d then add( [d, t2.y-d+t2.x], M)
Select in M the pairs with the smallest ordinates. Their abcissas are all
the possible answers to the problem.
If the solutions must be in integer values, it is possible to round
the coordinates of the points in M to the nearest integer(s), before
selecting the pairs with smallest ordinates. However some more
analysis is needed to check whether it can involve passing over a top,
and whether abcissas and ordinates are always integer simultaneously.
This is left to the reader as an exercise.
All bug reports are welcome.
