Return to Answer

Here is a graph:

g = RandomGraph[{20, 50}];

Here is the path between $\nu_l = 5$ and $\nu_n = 9$ (chosen arbitrarily):

mypathlist = FindPath[g, 5, 9][[1]]

(* {5, 2, 3, 6, 4, 1, 18, 10, 7, 9} *)

Here are two points along that path chosen arbitrarily:

myvertexes = RandomSample[mypathlist, 2]

(* {2, 7} *)

Here is the shortest path in $g$ between these vertexes:

mynewpathsegment = 
 FindShortestPath[g, myvertexes[[1]], myvertexes[[2]]]

(* {2,7} *)

Here is the original path with the new shortest path replacing the existing path segment:

mypathlist /. 
{x__, PatternSequence[myvertexes[[1]], __, myvertexes[[2]]], z__} -> 
{x, Sequence[myvertexes[[1]], myvertexes[[2]]], z}

(* {5, 2, 7, 9} *)

Note that this code automatically and randomly selects one of the shortest paths, if there are indeed multiple shortest paths. You can verify this with this simple example:

gg = Graph[{1 -> 2, 1 -> 3, 3 -> 4, 2 -> 4}]

FindShortestPath[gg, 1, 4]

(* {1, 2, 4} *)

(but not {1,3,4}).

Here is a graph:

g = RandomGraph[{20, 50}];

Here is the path between $\nu_l = 5$ and $\nu_n = 9$ (chosen arbitrarily):

mypathlist = FindPath[g, 5, 9][[1]]

(* {5, 2, 3, 6, 4, 1, 18, 10, 7, 9} *)

Here are two points along that path chosen arbitrarily:

myvertexes = RandomSample[mypathlist, 2]

(* {2, 7} *)

Here is the shortest path in $g$ between these vertexes:

mynewpathsegment = 
 FindShortestPath[g, myvertexes[[1]], myvertexes[[2]]]

(* {2,7} *)

If you want to get all such shortest paths:

myshortestlist = FindPath[gg, myvertexes[[1]], myvertexes[[2]], {GraphDistance[g, myvertexes[[1]], myvertexes[[2]]]}, All]

Then choose one of these shortest paths randomly:

myfinalshortpath = RandomChoice[myshortestlist]

Here is the original path with the new shortest path replacing the existing path segment:

mypathlist /. 
{x__, PatternSequence[myvertexes[[1]], __, myvertexes[[2]]], z__} -> 
{x, Sequence[myvertexes[[1]], myvertexes[[2]]], z}

(* {5, 2, 7, 9} *)

Note that this code automatically selects one of the shortest paths, if there are indeed multiple shortest paths. You can verify this with this simple example:

gg = Graph[{1 -> 2, 1 -> 3, 3 -> 4, 2 -> 4}]

FindShortestPath[gg, 1, 4]

(* {1, 2, 4} *)

(but not {1,3,4}).

Here is a graph:

g = RandomGraph[{20, 50}];

Here is the path between $\nu_l = 5$ and $\nu_n = 9$ (chosen arbitrarily):

mypathlist = FindPath[g, 5, 9][[1]]

(* {5, 2, 3, 6, 4, 1, 18, 10, 7, 9} *)

Here are two points along that path chosen arbitrarily:

myvertexes = RandomSample[mypathlist, 2]

(* {2, 7} *)

Here is the shortest path in $g$ between these vertexes:

mynewpathsegment = 
 FindShortestPath[g, myvertexes[[1]], myvertexes[[2]]]

(* {2,7} *)

Here is the original path with the new shortest path replacing the existing path segment:

mypathlist /. 
{x__, PatternSequence[myvertexes[[1]], __, myvertexes[[2]]], z__} -> 
{x, Sequence[myvertexes[[1]], myvertexes[[2]]], z}

(* {5, 2, 7, 9} *)

Here is a graph:

g = RandomGraph[{20, 50}];

Here is the path between $\nu_l = 5$ and $\nu_n = 9$ (chosen arbitrarily):

mypathlist = FindPath[g, 5, 9][[1]]

(* {5, 2, 3, 6, 4, 1, 18, 10, 7, 9} *)

Here are two points along that path chosen arbitrarily:

myvertexes = RandomSample[mypathlist, 2]

(* {2, 7} *)

Here is the shortest path in $g$ between these vertexes:

mynewpathsegment = 
 FindShortestPath[g, myvertexes[[1]], myvertexes[[2]]]

(* {2,7} *)

Here is the original path with the new shortest path replacing the existing path segment:

mypathlist /. 
{x__, PatternSequence[myvertexes[[1]], __, myvertexes[[2]]], z__} -> 
{x, Sequence[myvertexes[[1]], myvertexes[[2]]], z}

(* {5, 2, 7, 9} *)

Note that this code automatically and randomly selects one of the shortest paths, if there are indeed multiple shortest paths. You can verify this with this simple example:

gg = Graph[{1 -> 2, 1 -> 3, 3 -> 4, 2 -> 4}]

FindShortestPath[gg, 1, 4]

(* {1, 2, 4} *)

(but not {1,3,4}).

Here is a graph:

g = RandomGraph[{20, 50}];

Here is the path between $\nu_l = 5$ and $\nu_n = 9$ (chosen arbitrarily):

mypathlist = FindPath[g, 5, 9][[1]]

(* {5, 2, 3, 6, 4, 1, 18, 10, 7, 9} *)

Here are two points along that path chosen arbitrarily:

myvertexes = RandomSample[mypathlist, 2]

(* {2, 7} *)

Here is the shortest path in $g$ between these vertexes:

mynewpathsegment = 
 FindShortestPath[g, myvertexes[[1]], myvertexes[[2]]]

(* {2,7} *)

Here is the original path with the new shortest path replacing the existing path segment:

(* {5, 2, 7, 9} *)

Here is a graph:

g = RandomGraph[{20, 50}];

Here is the path between $\nu_l = 5$ and $\nu_n = 9$ (chosen arbitrarily):

mypathlist = FindPath[g, 5, 9][[1]]

(* {5, 2, 3, 6, 4, 1, 18, 10, 7, 9} *)

Here are two points along that path chosen arbitrarily:

myvertexes = RandomSample[mypathlist, 2]

(* {2, 7} *)

Here is the shortest path in $g$ between these vertexes:

mynewpathsegment = 
 FindShortestPath[g, myvertexes[[1]], myvertexes[[2]]]

(* {2,7} *)

Here is the original path with the new shortest path replacing the existing path segment:

mypathlist /. 
{x__, PatternSequence[myvertexes[[1]], __, myvertexes[[2]]], z__} -> 
{x, Sequence[myvertexes[[1]], myvertexes[[2]]], z}

(* {5, 2, 7, 9} *)