Edge disjoint shortest pair algorithm - Revision history

Mazewaxie: WP:GENFIXES

2024-03-31T21:18:51Z

Citation bot: Alter: pages. Add: authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Computer network stubs | #UCB_Category 226/547

2023-12-21T18:44:26Z

Alter: pages. Add: authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Computer network stubs | #UCB_Category 226/547

← Previous revision		Revision as of 18:44, 21 December 2023
Line 1:		Line 1:
	{{more citations needed\|date=January 2010}}		{{more citations needed\|date=January 2010}}
	'''Edge disjoint shortest pair algorithm''' is an [[algorithm]] in [[computer network]] [[routing]].<ref>{{cite book\|last=Bhandari\|first=Ramesh\|title=Survivable networks: algorithms for diverse routing\|publisher=Springer\|year=1999\|~~ISBN~~=0-7923-8381-8\|volume=\|pages=46}}</ref> The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of [[vertex (graph theory)\|vertices]]. For an undirected graph G(V, E), it is stated as follows:		'''Edge disjoint shortest pair algorithm''' is an [[algorithm]] in [[computer network]] [[routing]].<ref>{{cite book\|last=Bhandari\|first=Ramesh\|title=Survivable networks: algorithms for diverse routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|volume=\|pages=46}}</ref> The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of [[vertex (graph theory)\|vertices]]. For an undirected graph G(V, E), it is stated as follows:

	# Run the shortest path algorithm for the given pair of vertices		# Run the shortest path algorithm for the given pair of vertices
Line 7:		Line 7:
	# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''		# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''
	# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results.		# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results.
	In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|~~last~~=Jones\|~~first~~=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=~~21-37~~}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm.<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=~~159-162~~}}</ref> Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).		In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last1=Jones\|first1=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21–37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm.<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159–162}}</ref> Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).

	==The Modified Dijkstra Algorithm==		==The Modified Dijkstra Algorithm==

RJFJR: /* The Modified Dijkstra AlgorithmBhandari, Ramesh (1994), “Optimal Diverse Routing in Telecommunication Fiber Networks”, Proc. of IEEE INFOCOM, Toronto, Canada, pp. 1498-1508. */ move ref out of heading

2023-11-21T05:19:40Z

The Modified Dijkstra AlgorithmBhandari, Ramesh (1994), “Optimal Diverse Routing in Telecommunication Fiber Networks”, Proc. of IEEE INFOCOM, Toronto, Canada, pp. 1498-1508.: move ref out of heading

← Previous revision		Revision as of 05:19, 21 November 2023
Line 9:		Line 9:
	In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last=Jones\|first=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21-37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm.<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159-162}}</ref> Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).		In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last=Jones\|first=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21-37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm.<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159-162}}</ref> Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).

	==The Modified Dijkstra Algorithm<ref name=":0" /><ref>Bhandari, Ramesh (1994), “Optimal Diverse Routing in Telecommunication Fiber Networks”, ''Proc. of IEEE INFOCOM'', Toronto, Canada, pp. 1498-1508.</ref>==		==The Modified Dijkstra Algorithm==
			Source:<ref name=":0" /><ref>Bhandari, Ramesh (1994), “Optimal Diverse Routing in Telecommunication Fiber Networks”, ''Proc. of IEEE INFOCOM'', Toronto, Canada, pp. 1498-1508.</ref>

	G = (V, E)		G = (V, E)
	d(i) – the distance of vertex i (i∈V) from source vertex A; it is the sum of arcs in a possible		d(i) – the distance of vertex i (i∈V) from source vertex A; it is the sum of arcs in a possible

ZI Jony: v2.04b - Fix errors for CW project (Link with encoded space)

2022-03-15T06:01:34Z

v2.04b - Fix errors for CW project (Link with encoded space)

← Previous revision		Revision as of 06:01, 15 March 2022
Line 49:		Line 49:
	In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<\|V\|), the efficiency is O(d\|V\|), being O(\|V\|<sup>2</sup>), in the worst case, as in the traditional Dijkstra's case.		In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<\|V\|), the efficiency is O(d\|V\|), being O(\|V\|<sup>2</sup>), in the worst case, as in the traditional Dijkstra's case.

	In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d<sup>2</sup>\|V\|), being O(\|V\|<sup>3</sup>) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(\|V\|) (or, equivalently, O(\|E\|)). The edge-disjoint shortest pair algorithm then becomes comparable in efficiency to the [[Suurballe's algorithm]], which in general is of O(\|V\|<sup>2</sup>) due to an extra graph transformation that reweights the graph to avoid negative cost arcs, allowing [[Dijkstra's algorithm]] to be used for both shortest path steps. The reweighting requires building the entire shortest path tree rooted at the source vertex. By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs. The ensuing simple form further lends itself to easy extensions<ref>[[Edge disjoint shortest pair algorithm#cite~~%20ref~~-8\|↑]] Bhandari, Ramesh (1997) “Optimal Physically-Disjoint Paths Algorithms and Survivable Networks”, ''Proc. of Second IEEE Symposium on Computer and Communications'', Alexandria, Egypt, pp. 433-441.</ref><ref>{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=175-182, 93-162}}</ref> to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real-life networks.		In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d<sup>2</sup>\|V\|), being O(\|V\|<sup>3</sup>) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(\|V\|) (or, equivalently, O(\|E\|)). The edge-disjoint shortest pair algorithm then becomes comparable in efficiency to the [[Suurballe's algorithm]], which in general is of O(\|V\|<sup>2</sup>) due to an extra graph transformation that reweights the graph to avoid negative cost arcs, allowing [[Dijkstra's algorithm]] to be used for both shortest path steps. The reweighting requires building the entire shortest path tree rooted at the source vertex. By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs. The ensuing simple form further lends itself to easy extensions<ref>[[Edge disjoint shortest pair algorithm#cite ref-8\|↑]] Bhandari, Ramesh (1997) “Optimal Physically-Disjoint Paths Algorithms and Survivable Networks”, ''Proc. of Second IEEE Symposium on Computer and Communications'', Alexandria, Egypt, pp. 433-441.</ref><ref>{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=175-182, 93-162}}</ref> to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real-life networks.

	The vertex disjoint version of the above edge-disjoint shortest pair of paths algorithm is obtained by splitting each vertex (except for the source and destination vertices) of the first shortest path in Step 3 of the algorithm, connecting the split vertex pair by a zero weight arc (directed towards the source vertex), and replacing any incident edge with two oppositely directed arcs, one incident on the vertex of the split pair (closer to the source vertex) and the other arc emanating from the other vertex. The K (>2) versions are similarly obtained, e.g., the vertices of the shortest edge disjoint pair of paths (except for the source and destination vertices) are split, with the vertices in each split pair connected to each other with arcs of zero weight as well as the external edges in a similar manner<sup>[8][9]</sup>. The algorithms presented for undirected graphs also extend to directed graphs, and apply in general to any problem (in any technical discipline) that can be modeled as a graph of vertices and edges (or arcs).		The vertex disjoint version of the above edge-disjoint shortest pair of paths algorithm is obtained by splitting each vertex (except for the source and destination vertices) of the first shortest path in Step 3 of the algorithm, connecting the split vertex pair by a zero weight arc (directed towards the source vertex), and replacing any incident edge with two oppositely directed arcs, one incident on the vertex of the split pair (closer to the source vertex) and the other arc emanating from the other vertex. The K (>2) versions are similarly obtained, e.g., the vertices of the shortest edge disjoint pair of paths (except for the source and destination vertices) are split, with the vertices in each split pair connected to each other with arcs of zero weight as well as the external edges in a similar manner<sup>[8][9]</sup>. The algorithms presented for undirected graphs also extend to directed graphs, and apply in general to any problem (in any technical discipline) that can be modeled as a graph of vertices and edges (or arcs).

WikiCleanerBot: v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2021-11-03T05:03:07Z

v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 05:03, 3 November 2021
Line 7:		Line 7:
	# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''		# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''
	# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results.		# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results.
	In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last=Jones\|first=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21-37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159-162}}</ref>. Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).		In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last=Jones\|first=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21-37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm.<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159-162}}</ref> Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).

	==The Modified Dijkstra Algorithm<ref name=":0" /><ref>Bhandari, Ramesh (1994), “Optimal Diverse Routing in Telecommunication Fiber Networks”, ''Proc. of IEEE INFOCOM'', Toronto, Canada, pp. 1498-1508.</ref>==		==The Modified Dijkstra Algorithm<ref name=":0" /><ref>Bhandari, Ramesh (1994), “Optimal Diverse Routing in Telecommunication Fiber Networks”, ''Proc. of IEEE INFOCOM'', Toronto, Canada, pp. 1498-1508.</ref>==

Scientist11111: Added material on extension to vertex-disjointness and directed graphs within the Discussion section. References appear to be adequate.

2021-11-02T20:02:47Z

Added material on extension to vertex-disjointness and directed graphs within the Discussion section. References appear to be adequate.

← Previous revision		Revision as of 20:02, 2 November 2021
Line 6:		Line 6:
	# Make the length of each of the above arcs negative		# Make the length of each of the above arcs negative
	# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''		# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''
	# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the ~~sink~~ vertex now. The desired pair of paths results.		# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results.
	In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last=Jones\|first=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21-37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159-162}}</ref>. Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).		In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last=Jones\|first=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21-37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159-162}}</ref>. Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).

Line 49:		Line 49:
	In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<\|V\|), the efficiency is O(d\|V\|), being O(\|V\|<sup>2</sup>), in the worst case, as in the traditional Dijkstra's case.		In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<\|V\|), the efficiency is O(d\|V\|), being O(\|V\|<sup>2</sup>), in the worst case, as in the traditional Dijkstra's case.

	In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d<sup>2</sup>\|V\|), being O(\|V\|<sup>3</sup>) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(\|V\|) (or, equivalently, O(\|E\|)). The edge-disjoint shortest pair algorithm then becomes comparable in efficiency to the [[Suurballe's algorithm]], which in general ~~solves~~ ~~the~~ ~~same~~ ~~problem~~ ~~more~~ ~~quickly~~ by ~~reweighting~~ ~~the~~ ~~edges~~ of the graph to avoid negative ~~costs~~, allowing [[Dijkstra's algorithm]] to be used for both shortest path steps. The reweighting ~~is done via a graph transformation, which~~ requires building the entire shortest path tree rooted at the source vertex. By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs. The ensuing simple form further lends itself to easy extensions<ref>[[Edge disjoint shortest pair algorithm#cite%20ref-8\|↑]] Bhandari, Ramesh (1997) “Optimal Physically-Disjoint Paths Algorithms and Survivable Networks”, ''Proc. of Second IEEE Symposium on Computer and Communications'', Alexandria, Egypt, pp. 433-441.</ref><ref>{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=175-182, 93-162}}</ref> to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real-life networks.		In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d<sup>2</sup>\|V\|), being O(\|V\|<sup>3</sup>) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(\|V\|) (or, equivalently, O(\|E\|)). The edge-disjoint shortest pair algorithm then becomes comparable in efficiency to the [[Suurballe's algorithm]], which in general is of O(\|V\|<sup>2</sup>) due to an extra graph transformation that reweights the graph to avoid negative cost arcs, allowing [[Dijkstra's algorithm]] to be used for both shortest path steps. The reweighting requires building the entire shortest path tree rooted at the source vertex. By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs. The ensuing simple form further lends itself to easy extensions<ref>[[Edge disjoint shortest pair algorithm#cite%20ref-8\|↑]] Bhandari, Ramesh (1997) “Optimal Physically-Disjoint Paths Algorithms and Survivable Networks”, ''Proc. of Second IEEE Symposium on Computer and Communications'', Alexandria, Egypt, pp. 433-441.</ref><ref>{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=175-182, 93-162}}</ref> to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real-life networks.

			The vertex disjoint version of the above edge-disjoint shortest pair of paths algorithm is obtained by splitting each vertex (except for the source and destination vertices) of the first shortest path in Step 3 of the algorithm, connecting the split vertex pair by a zero weight arc (directed towards the source vertex), and replacing any incident edge with two oppositely directed arcs, one incident on the vertex of the split pair (closer to the source vertex) and the other arc emanating from the other vertex. The K (>2) versions are similarly obtained, e.g., the vertices of the shortest edge disjoint pair of paths (except for the source and destination vertices) are split, with the vertices in each split pair connected to each other with arcs of zero weight as well as the external edges in a similar manner<sup>[8][9]</sup>. The algorithms presented for undirected graphs also extend to directed graphs, and apply in general to any problem (in any technical discipline) that can be modeled as a graph of vertices and edges (or arcs).

	==References==		==References==

Bruce1ee: fixed lint errors – file options

2021-10-23T15:57:44Z

fixed lint errors – file options

← Previous revision		Revision as of 15:57, 23 October 2021
Line 34:		Line 34:

	== Example ==		== Example ==
	The main steps of the edge-disjoint shortest pair algorithm are illustrated below:[[File:Bhandari's Shortest Pair of Edge-Disjoint Shortest Paths Algorithm.jpg~~\|center~~\|center\|600px\|Graphical Illustration of the Shortest Pair of Disjoint Paths Algorithm]]Figure A shows the given undirected graph G(V, E) with edge weights.		The main steps of the edge-disjoint shortest pair algorithm are illustrated below:[[File:Bhandari's Shortest Pair of Edge-Disjoint Shortest Paths Algorithm.jpg\|center\|600px\|Graphical Illustration of the Shortest Pair of Disjoint Paths Algorithm]]Figure A shows the given undirected graph G(V, E) with edge weights.

	Figure B displays the calculated shortest path ABCZ from A to Z (in bold lines).		Figure B displays the calculated shortest path ABCZ from A to Z (in bold lines).

Scientist11111: 1) Corrected a few typographical errors. 2) Corrected the heading, "Algorithm" to "The Modified Dijkstra Algorithm", which is the appropriate description. 3) Illustrated the edge-disjoint pair algorithm with an example. 4) Provided a discussion of the presented edge-disjoint shortest pair algorithm, including its usefulness.

2021-10-22T23:48:44Z

1) Corrected a few typographical errors. 2) Corrected the heading, "Algorithm" to "The Modified Dijkstra Algorithm", which is the appropriate description. 3) Illustrated the edge-disjoint pair algorithm with an example. 4) Provided a discussion of the presented edge-disjoint shortest pair algorithm, including its usefulness.

← Previous revision		Revision as of 23:48, 22 October 2021
Line 1:		Line 1:
	{{more citations needed\|date=January 2010}}		{{more citations needed\|date=January 2010}}
	'''Edge disjoint shortest pair algorithm''' is an [[algorithm]] in [[computer network]] [[routing]].<ref>{{cite book\|title=Survivable networks: algorithms for diverse routing~~\|volume=477\|first=Ramesh \|last=Bhandari~~ \|publisher =Springer\|year= 1999 \|ISBN =0-7923-8381-8 \|pages=46}}</ref> The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of [[vertex (graph theory)\|vertices]] as follows:		'''Edge disjoint shortest pair algorithm''' is an [[algorithm]] in [[computer network]] [[routing]].<ref>{{cite book\|last=Bhandari\|first=Ramesh\|title=Survivable networks: algorithms for diverse routing\|publisher=Springer\|year=1999\|ISBN=0-7923-8381-8\|volume=\|pages=46}}</ref> The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of [[vertex (graph theory)\|vertices]]. For an undirected graph G(V, E), it is stated as follows:

	* Run the shortest path algorithm for the given pair of vertices		# Run the shortest path algorithm for the given pair of vertices
	* Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex		# Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex
	* Make the length of each of the above arcs negative		# Make the length of each of the above arcs negative
	* Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''		# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''
	* Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the sink vertex now. The desired pair of paths results.		# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the sink vertex now. The desired pair of paths results.
			In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last=Jones\|first=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21-37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159-162}}</ref>. Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).

			==The Modified Dijkstra Algorithm<ref name=":0" /><ref>Bhandari, Ramesh (1994), “Optimal Diverse Routing in Telecommunication Fiber Networks”, ''Proc. of IEEE INFOCOM'', Toronto, Canada, pp. 1498-1508.</ref>==
	[[Suurballe's algorithm]] solves the same problem more quickly by reweighting the edges of the graph to avoid negative costs, allowing [[Dijkstra's algorithm]] to be used for both shortest path steps.

	==Algorithm==
	G = (V, E)		G = (V, E)
	d(i) – the distance of vertex i (i∈V) from source vertex A; it's the sum of arcs in a possible		d(i) – the distance of vertex i (i∈V) from source vertex A; it is the sum of arcs in a possible
	path from vertex A to vertex i. Note that d(A)=0;		path from vertex A to vertex i. Note that d(A)=0;
	P(i) – the predecessor of vertex I on the same path.		P(i) – the predecessor of vertex i on the same path.
	Z – the destination vertex		Z – the destination vertex

	Step 1.		Step 1.
	Start with d(A) = 0,		Start with d(A) = 0,
	d(i) = l (Ai), if ~~i∈ΓA~~; Γi ≡ set of neighbor vertices of vertex i, l(ij) = length of arc from vertex i to vertex j.		d(i) = l (Ai), if i∈Γ<sub>A</sub>; Γ<sub>i</sub> ≡ set of neighbor vertices of vertex i, l(ij) = length of arc from vertex i to vertex j.

	= ∞, otherwise ~~(∞ is a large number defined below);~~		= ∞, otherwise.
	Assign S = V-~~<nowiki/>~~{A}, where V is the set of vertices in the given graph.		Assign S = V-{A}, where V is the set of vertices in the given graph.
	Assign P(i) = A, ∀i∈S.		Assign P(i) = A, ∀i∈S.
	Step 2.		Step 2.
Line 29:		Line 28:
	c) If j = Z (the destination vertex), END; otherwise go to Step 3.		c) If j = Z (the destination vertex), END; otherwise go to Step 3.
	Step 3.		Step 3.
	~~∀i∈Γj~~, if d(j) + l(ij) < d(i),		∀i∈Γ<sub>j</sub>, if d(j) + l(ji) < d(i),
	a) set d(i) = d(j) + l(ij), P(i) = j.		a) set d(i) = d(j) + l(ji), P(i) = j.
	b) S = S ∪{i}		b) S = S ∪{i}
	Go to Step 2.		Go to Step 2.

			== Example ==
			The main steps of the edge-disjoint shortest pair algorithm are illustrated below:[[File:Bhandari's Shortest Pair of Edge-Disjoint Shortest Paths Algorithm.jpg\|center\|center\|600px\|Graphical Illustration of the Shortest Pair of Disjoint Paths Algorithm]]Figure A shows the given undirected graph G(V, E) with edge weights.

			Figure B displays the calculated shortest path ABCZ from A to Z (in bold lines).

			Figure C shows the reversal of the arcs of the shortest path and their negative weights.

			Figure D displays the shortest path ADCBZ from A to Z determined in the new transformed. graph of Figure C (this is determined using the modified Dijkstra algorithm (or the BFS algorithm) valid for such negative arcs; there are never any negative cycles in such a transformed graph).

			Figure E displays the determined shortest path ADCBZ in the original graph.

			Figure F displays the determined shortest pair of edge-disjoint paths (ABZ, ADCZ) found after erasing the edge BC common to paths ABCZ and ADCBZ, and grouping the remaining edges suitably.

			== Discussion ==
			In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<\|V\|), the efficiency is O(d\|V\|), being O(\|V\|<sup>2</sup>), in the worst case, as in the traditional Dijkstra's case.

			In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d<sup>2</sup>\|V\|), being O(\|V\|<sup>3</sup>) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(\|V\|) (or, equivalently, O(\|E\|)). The edge-disjoint shortest pair algorithm then becomes comparable in efficiency to the [[Suurballe's algorithm]], which in general solves the same problem more quickly by reweighting the edges of the graph to avoid negative costs, allowing [[Dijkstra's algorithm]] to be used for both shortest path steps. The reweighting is done via a graph transformation, which requires building the entire shortest path tree rooted at the source vertex. By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs. The ensuing simple form further lends itself to easy extensions<ref>[[Edge disjoint shortest pair algorithm#cite%20ref-8\|↑]] Bhandari, Ramesh (1997) “Optimal Physically-Disjoint Paths Algorithms and Survivable Networks”, ''Proc. of Second IEEE Symposium on Computer and Communications'', Alexandria, Egypt, pp. 433-441.</ref><ref>{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=175-182, 93-162}}</ref> to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real-life networks.

	==References==		==References==

Frap: /* Algorithm */

2019-12-25T00:17:28Z

Algorithm

← Previous revision		Revision as of 00:17, 25 December 2019
Line 18:		Line 18:

	Step 1.		Step 1.
	Start with d(A)=0,		Start with d(A) = 0,
	d(i) = l (Ai), if i∈ΓA; Γi ≡ set of neighbor vertices of vertex i,l(ij) = length of arc from vertex i to vertex j.		d(i) = l (Ai), if i∈ΓA; Γi ≡ set of neighbor vertices of vertex i, l(ij) = length of arc from vertex i to vertex j.

	= ∞, otherwise (∞ is a large number defined below);		= ∞, otherwise (∞ is a large number defined below);
	Assign S = V-<nowiki/>{A}, where V is the set of vertices in the given graph.		Assign S = V-<nowiki/>{A}, where V is the set of vertices in the given graph.
	Assign P(i) = A, ∀i∈S.		Assign P(i) = A, ∀i∈S.
	Step 2.		Step 2.
	a) Find j∈S such that d(j) = min d(i), i∈S.		a) Find j∈S such that d(j) = min d(i), i∈S.
	b) Set S = S – {j}.		b) Set S = S – {j}.
	c) If j = Z (the destination vertex), END; otherwise go to Step 3.		c) If j = Z (the destination vertex), END; otherwise go to Step 3.
	Step 3.		Step 3.
	∀i∈Γj, if d(j)+l(ij)<d(i),		∀i∈Γj, if d(j) + l(ij) < d(i),
	a) set d(i) = d(j) + l(ij), P(i) = j.		a) set d(i) = d(j) + l(ij), P(i) = j.
	b) S = S ∪{i}		b) S = S ∪{i}
	Go to Step 2.		Go to Step 2.

	==References==		==References==

Adavidb: clean up, typo(s) fixed: it’s → it's

2019-03-06T02:13:10Z

clean up, typo(s) fixed: it’s → it's

← Previous revision		Revision as of 02:13, 6 March 2019
Line 1:		Line 1:
	{{~~refimprove~~\|date=January 2010}}		{{more citations needed\|date=January 2010}}
	'''Edge disjoint shortest pair algorithm''' is an [[algorithm]] in [[computer network]] [[routing]].<ref>{{cite book\|title=Survivable networks: algorithms for diverse routing\|volume=477\|first=Ramesh \|last=Bhandari \|publisher =Springer\|year= 1999 \|ISBN =0-7923-8381-8 \|pages=46}}</ref> The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of [[vertex (graph theory)\|vertices]] as follows:		'''Edge disjoint shortest pair algorithm''' is an [[algorithm]] in [[computer network]] [[routing]].<ref>{{cite book\|title=Survivable networks: algorithms for diverse routing\|volume=477\|first=Ramesh \|last=Bhandari \|publisher =Springer\|year= 1999 \|ISBN =0-7923-8381-8 \|pages=46}}</ref> The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of [[vertex (graph theory)\|vertices]] as follows:

Line 12:		Line 12:
	==Algorithm==		==Algorithm==
	G = (V, E)		G = (V, E)
	d(i) – the distance of vertex i (i∈V) from source vertex A; ~~it’s~~ the sum of arcs in a possible		d(i) – the distance of vertex i (i∈V) from source vertex A; it's the sum of arcs in a possible
	path from vertex A to vertex i. Note that d(A)=0;		path from vertex A to vertex i. Note that d(A)=0;
	P(i) – the predecessor of vertex I on the same path.		P(i) – the predecessor of vertex I on the same path.

← Previous revision		Revision as of 21:18, 31 March 2024
Line 1:		Line 1:
	{{more citations needed\|date=January 2010}}		{{more citations needed\|date=January 2010}}
	'''Edge disjoint shortest pair algorithm''' is an [[algorithm]] in [[computer network]] [[routing]].<ref>{{cite book\|last=Bhandari\|first=Ramesh\|title=Survivable networks: algorithms for diverse routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|volume=\|pages=46}}</ref> The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of [[vertex (graph theory)\|vertices]]. For an undirected graph G(V, E), it is stated as follows:		'''Edge disjoint shortest pair algorithm''' is an [[algorithm]] in [[computer network]] [[routing]].<ref>{{cite book\|last=Bhandari\|first=Ramesh\|title=Survivable networks: algorithms for diverse routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|volume=\|pages=46}}</ref> The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of [[vertex (graph theory)\|vertices]]. For an undirected graph G(V, E), it is stated as follows:

	# Run the shortest path algorithm for the given pair of vertices		# Run the shortest path algorithm for the given pair of vertices
Line 7:		Line 7:
	# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''		# Run the shortest path algorithm ''(Note: the algorithm should accept negative costs)''
	# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results.		# Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results.
	In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last1=Jones\|first1=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21–37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm.<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292 </ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159–162}}</ref> Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).		In lieu of the general purpose Ford's shortest path algorithm<ref>{{Cite book\|last=Ford\|first=L. R.\|title=Network Flow Theory, Report P-923\|publisher=Rand Corporation\|year=1956\|location=Santa Monica, California}}</ref><ref>{{Cite book\|last1=Jones\|first1=R. H.\|title=Mathematics in Communication Theory\|last2=Steele\|first2=N. C.\|publisher=Ellis Harwood (division of John Wiley & Sons)\|year=1989\|isbn=0-470-21246-2\|location=Chichester\|pages=74}}</ref> valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari<ref name=":0">{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=21–37}}</ref> provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional [[Dijkstra's algorithm]], and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm.<ref>E. F. Moore (1959) "The Shortest Path through the Maze", ''Proceedings of the International Symposium on the Theory of Switching, Part II'', Harvard University Press, p. 285-292</ref><ref>{{Cite book\|last=Kershenbaum\|first=Aaron\|title=Telecommunications Network Design Algorithms\|publisher=McGraw-Hill\|year=1993\|isbn=0-07-034228-8\|pages=159–162}}</ref> Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).

	==The Modified Dijkstra Algorithm==		==The Modified Dijkstra Algorithm==
Line 36:		Line 36:

	== Example ==		== Example ==
	The main steps of the edge-disjoint shortest pair algorithm are illustrated below:[[File:Bhandari's Shortest Pair of Edge-Disjoint Shortest Paths Algorithm.jpg\|center\|600px\|Graphical Illustration of the Shortest Pair of Disjoint Paths Algorithm]]Figure A shows the given undirected graph G(V, E) with edge weights.		The main steps of the edge-disjoint shortest pair algorithm are illustrated below:[[File:Bhandari's Shortest Pair of Edge-Disjoint Shortest Paths Algorithm.jpg\|center\|600px\|Graphical Illustration of the Shortest Pair of Disjoint Paths Algorithm]]Figure A shows the given undirected graph G(V, E) with edge weights.

	Figure B displays the calculated shortest path ABCZ from A to Z (in bold lines).		Figure B displays the calculated shortest path ABCZ from A to Z (in bold lines).

	Figure C shows the reversal of the arcs of the shortest path and their negative weights.		Figure C shows the reversal of the arcs of the shortest path and their negative weights.

	Figure D displays the shortest path ADCBZ from A to Z determined in the new transformed. graph of Figure C (this is determined using the modified Dijkstra algorithm (or the BFS algorithm) valid for such negative arcs; there are never any negative cycles in such a transformed graph).		Figure D displays the shortest path ADCBZ from A to Z determined in the new transformed. graph of Figure C (this is determined using the modified Dijkstra algorithm (or the BFS algorithm) valid for such negative arcs; there are never any negative cycles in such a transformed graph).

	Figure E displays the determined shortest path ADCBZ in the original graph.		Figure E displays the determined shortest path ADCBZ in the original graph.

	Figure F displays the determined shortest pair of edge-disjoint paths (ABZ, ADCZ) found after erasing the edge BC common to paths ABCZ and ADCBZ, and grouping the remaining edges suitably.		Figure F displays the determined shortest pair of edge-disjoint paths (ABZ, ADCZ) found after erasing the edge BC common to paths ABCZ and ADCBZ, and grouping the remaining edges suitably.
Line 51:		Line 51:
	In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<\|V\|), the efficiency is O(d\|V\|), being O(\|V\|<sup>2</sup>), in the worst case, as in the traditional Dijkstra's case.		In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<\|V\|), the efficiency is O(d\|V\|), being O(\|V\|<sup>2</sup>), in the worst case, as in the traditional Dijkstra's case.

	In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d<sup>2</sup>\|V\|), being O(\|V\|<sup>3</sup>) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(\|V\|) (or, equivalently, O(\|E\|)). The edge-disjoint shortest pair algorithm then becomes comparable in efficiency to the [[Suurballe's algorithm]], which in general is of O(\|V\|<sup>2</sup>) due to an extra graph transformation that reweights the graph to avoid negative cost arcs, allowing [[Dijkstra's algorithm]] to be used for both shortest path steps. The reweighting requires building the entire shortest path tree rooted at the source vertex. By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs. The ensuing simple form further lends itself to easy extensions<ref>[[Edge disjoint shortest pair algorithm#cite ref-8\|↑]] Bhandari, Ramesh (1997) “Optimal Physically-Disjoint Paths Algorithms and Survivable Networks”, ''Proc. of Second IEEE Symposium on Computer and Communications'', Alexandria, Egypt, pp. 433-441.</ref><ref>{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=~~175-182~~, ~~93-162~~}}</ref> to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real-life networks.		In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d<sup>2</sup>\|V\|), being O(\|V\|<sup>3</sup>) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(\|V\|) (or, equivalently, O(\|E\|)). The edge-disjoint shortest pair algorithm then becomes comparable in efficiency to the [[Suurballe's algorithm]], which in general is of O(\|V\|<sup>2</sup>) due to an extra graph transformation that reweights the graph to avoid negative cost arcs, allowing [[Dijkstra's algorithm]] to be used for both shortest path steps. The reweighting requires building the entire shortest path tree rooted at the source vertex. By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs. The ensuing simple form further lends itself to easy extensions<ref>[[Edge disjoint shortest pair algorithm#cite ref-8\|↑]] Bhandari, Ramesh (1997) “Optimal Physically-Disjoint Paths Algorithms and Survivable Networks”, ''Proc. of Second IEEE Symposium on Computer and Communications'', Alexandria, Egypt, pp. 433-441.</ref><ref>{{Cite book\|last=Bhandari\|first=Ramesh\|title=Survivable Networks: Algorithms for Diverse Routing\|publisher=Springer\|year=1999\|isbn=0-7923-8381-8\|pages=175–182, 93–162}}</ref> to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real-life networks.

	The vertex disjoint version of the above edge-disjoint shortest pair of paths algorithm is obtained by splitting each vertex (except for the source and destination vertices) of the first shortest path in Step 3 of the algorithm, connecting the split vertex pair by a zero weight arc (directed towards the source vertex), and replacing any incident edge with two oppositely directed arcs, one incident on the vertex of the split pair (closer to the source vertex) and the other arc emanating from the other vertex. The K (>2) versions are similarly obtained, e.g., the vertices of the shortest edge disjoint pair of paths (except for the source and destination vertices) are split, with the vertices in each split pair connected to each other with arcs of zero weight as well as the external edges in a similar manner<sup>[8][9]</sup>. The algorithms presented for undirected graphs also extend to directed graphs, and apply in general to any problem (in any technical discipline) that can be modeled as a graph of vertices and edges (or arcs).		The vertex disjoint version of the above edge-disjoint shortest pair of paths algorithm is obtained by splitting each vertex (except for the source and destination vertices) of the first shortest path in Step 3 of the algorithm, connecting the split vertex pair by a zero weight arc (directed towards the source vertex), and replacing any incident edge with two oppositely directed arcs, one incident on the vertex of the split pair (closer to the source vertex) and the other arc emanating from the other vertex. The K (>2) versions are similarly obtained, e.g., the vertices of the shortest edge disjoint pair of paths (except for the source and destination vertices) are split, with the vertices in each split pair connected to each other with arcs of zero weight as well as the external edges in a similar manner<sup>[8][9]</sup>. The algorithms presented for undirected graphs also extend to directed graphs, and apply in general to any problem (in any technical discipline) that can be modeled as a graph of vertices and edges (or arcs).