Modification of Fords' Algorithm
$begingroup$
We were given a modification of Fords' algorithm that can detect negative cycles.
Note: $p$ is the predecessor function
Assume that, on the current iteration, arc $wv$ is corrected.
Consider the sequence $S = v, p(v), p(p(v)), . . .$ . Then
• either $r$ is the last element of $S$ (and there is no negative cycle so far),
• or $v$ appears in $S$ again (and a negative cycle is found).
THE QUESTION
Show that this modified Fords' algorithm solves the shortest path problem in
finite time by outputting either a negative cycle in $(G,c)$ or a shortest $r − v$ path for each $v ∈ V$ .
FORDS ALGORITHM
We assume that at a certain iteration of the algorithm, a potential $y ∈ Bbb R^V$ is given together with a map $p : V setminustext{{r}} → V$.
Call an arc $vw$ incorrect if $y_w > y_v + c(vw)$.
Ford’s algorithm starts with the potential $y$ and predecessor map $p$ that are given as
$y_r =0$, and $y_v =infty$, $p(v)=−1$ for every $v∈V$, $vne r$.
The element $−1$ is chosen arbitrarily. We could use any element or symbol
which does not belong to $V$ . Note also that $p(r)$ is undefined.
The algorithm repeats the following basic step: find an incorrect arc $vw$ and correct it by setting
$y_w =y_v +c(vw)$, $p(w)=v$.
It stops when all arcs are correct
As with all graph problems, I am not quite sure where to start with this one.
graph-theory optimization algorithms
asked Nov 8 '18 at 10:56
ʎpoqouʎpoqou
3101211
$endgroup$
add a comment |
$begingroup$
We were given a modification of Fords' algorithm that can detect negative cycles.
Note: $p$ is the predecessor function
Assume that, on the current iteration, arc $wv$ is corrected.
Consider the sequence $S = v, p(v), p(p(v)), . . .$ . Then
• either $r$ is the last element of $S$ (and there is no negative cycle so far),
• or $v$ appears in $S$ again (and a negative cycle is found).
THE QUESTION
Show that this modified Fords' algorithm solves the shortest path problem in
finite time by outputting either a negative cycle in $(G,c)$ or a shortest $r − v$ path for each $v ∈ V$ .
FORDS ALGORITHM
We assume that at a certain iteration of the algorithm, a potential $y ∈ Bbb R^V$ is given together with a map $p : V setminustext{{r}} → V$.
Call an arc $vw$ incorrect if $y_w > y_v + c(vw)$.
Ford’s algorithm starts with the potential $y$ and predecessor map $p$ that are given as
$y_r =0$, and $y_v =infty$, $p(v)=−1$ for every $v∈V$, $vne r$.
The element $−1$ is chosen arbitrarily. We could use any element or symbol
which does not belong to $V$ . Note also that $p(r)$ is undefined.
The algorithm repeats the following basic step: find an incorrect arc $vw$ and correct it by setting
$y_w =y_v +c(vw)$, $p(w)=v$.
It stops when all arcs are correct
As with all graph problems, I am not quite sure where to start with this one.
graph-theory optimization algorithms
asked Nov 8 '18 at 10:56
ʎpoqouʎpoqou
3101211
$endgroup$
$begingroup$
To get the ball rolling... On the first iteration where a repeated element is detected in the sequence $w,p(w),p(p(w)),...$ the repeated element has to be $w$. Otherwise the sequence $p(w),p(p(w)),...$ that was encountered on a previous iteration would contain a repeated element. Either the root $r$ is the last element of sequence $w,p(w),p(p(w)),...$ or $w$ appears in that sequence again.
$endgroup$
– ʎpoqou
Nov 8 '18 at 14:54
add a comment |
$begingroup$
We were given a modification of Fords' algorithm that can detect negative cycles.
Note: $p$ is the predecessor function
Assume that, on the current iteration, arc $wv$ is corrected.
Consider the sequence $S = v, p(v), p(p(v)), . . .$ . Then
• either $r$ is the last element of $S$ (and there is no negative cycle so far),
• or $v$ appears in $S$ again (and a negative cycle is found).
THE QUESTION
Show that this modified Fords' algorithm solves the shortest path problem in
finite time by outputting either a negative cycle in $(G,c)$ or a shortest $r − v$ path for each $v ∈ V$ .
FORDS ALGORITHM
We assume that at a certain iteration of the algorithm, a potential $y ∈ Bbb R^V$ is given together with a map $p : V setminustext{{r}} → V$.
Call an arc $vw$ incorrect if $y_w > y_v + c(vw)$.
Ford’s algorithm starts with the potential $y$ and predecessor map $p$ that are given as
$y_r =0$, and $y_v =infty$, $p(v)=−1$ for every $v∈V$, $vne r$.
The element $−1$ is chosen arbitrarily. We could use any element or symbol
which does not belong to $V$ . Note also that $p(r)$ is undefined.
The algorithm repeats the following basic step: find an incorrect arc $vw$ and correct it by setting
$y_w =y_v +c(vw)$, $p(w)=v$.
It stops when all arcs are correct
As with all graph problems, I am not quite sure where to start with this one.
graph-theory optimization algorithms
asked Nov 8 '18 at 10:56
ʎpoqouʎpoqou
3101211
$endgroup$
We were given a modification of Fords' algorithm that can detect negative cycles.
Note: $p$ is the predecessor function
Assume that, on the current iteration, arc $wv$ is corrected.
Consider the sequence $S = v, p(v), p(p(v)), . . .$ . Then
• either $r$ is the last element of $S$ (and there is no negative cycle so far),
• or $v$ appears in $S$ again (and a negative cycle is found).
THE QUESTION
Show that this modified Fords' algorithm solves the shortest path problem in
finite time by outputting either a negative cycle in $(G,c)$ or a shortest $r − v$ path for each $v ∈ V$ .
FORDS ALGORITHM
We assume that at a certain iteration of the algorithm, a potential $y ∈ Bbb R^V$ is given together with a map $p : V setminustext{{r}} → V$.
Call an arc $vw$ incorrect if $y_w > y_v + c(vw)$.
Ford’s algorithm starts with the potential $y$ and predecessor map $p$ that are given as
$y_r =0$, and $y_v =infty$, $p(v)=−1$ for every $v∈V$, $vne r$.
The element $−1$ is chosen arbitrarily. We could use any element or symbol
which does not belong to $V$ . Note also that $p(r)$ is undefined.
The algorithm repeats the following basic step: find an incorrect arc $vw$ and correct it by setting
$y_w =y_v +c(vw)$, $p(w)=v$.
It stops when all arcs are correct
As with all graph problems, I am not quite sure where to start with this one.
graph-theory optimization algorithms
graph-theory optimization algorithms
asked Nov 8 '18 at 10:56
ʎpoqouʎpoqou
3101211
asked Nov 8 '18 at 10:56
ʎpoqouʎpoqou
3101211
edited Nov 12 '18 at 11:44
ʎpoqou
asked Nov 8 '18 at 10:56
ʎpoqouʎpoqou
3101211
asked Nov 8 '18 at 10:56
ʎpoqouʎpoqou
3101211
asked Nov 8 '18 at 10:56
ʎpoqouʎpoqou
3101211
3101211
$begingroup$
To get the ball rolling... On the first iteration where a repeated element is detected in the sequence $w,p(w),p(p(w)),...$ the repeated element has to be $w$. Otherwise the sequence $p(w),p(p(w)),...$ that was encountered on a previous iteration would contain a repeated element. Either the root $r$ is the last element of sequence $w,p(w),p(p(w)),...$ or $w$ appears in that sequence again.
$endgroup$
– ʎpoqou
Nov 8 '18 at 14:54
add a comment |
$begingroup$
To get the ball rolling... On the first iteration where a repeated element is detected in the sequence $w,p(w),p(p(w)),...$ the repeated element has to be $w$. Otherwise the sequence $p(w),p(p(w)),...$ that was encountered on a previous iteration would contain a repeated element. Either the root $r$ is the last element of sequence $w,p(w),p(p(w)),...$ or $w$ appears in that sequence again.
$endgroup$
– ʎpoqou
Nov 8 '18 at 14:54
$begingroup$
To get the ball rolling... On the first iteration where a repeated element is detected in the sequence $w,p(w),p(p(w)),...$ the repeated element has to be $w$. Otherwise the sequence $p(w),p(p(w)),...$ that was encountered on a previous iteration would contain a repeated element. Either the root $r$ is the last element of sequence $w,p(w),p(p(w)),...$ or $w$ appears in that sequence again.
$endgroup$
– ʎpoqou
Nov 8 '18 at 14:54
$begingroup$
To get the ball rolling... On the first iteration where a repeated element is detected in the sequence $w,p(w),p(p(w)),...$ the repeated element has to be $w$. Otherwise the sequence $p(w),p(p(w)),...$ that was encountered on a previous iteration would contain a repeated element. Either the root $r$ is the last element of sequence $w,p(w),p(p(w)),...$ or $w$ appears in that sequence again.
$endgroup$
– ʎpoqou
Nov 8 '18 at 14:54
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Answering my own question following the posting of solutions...
We only need to show that if $(G, c)$ contains a negative cycle, then the modified algorithm finds it.
We use induction on iteration $q$.
Case $q = 1$ is trivial.
Assume no negative cycle has been found up to (and including) iteration $q − 1$, and on iteration $q$ arc $wv$ was corrected, so $p(v) = w$. On the (backward) path $Q = w,p(w),p(p(w)),...$ there is no repetion (by induction) so its last element is $r$. The path $P = v,p(v),p(p(v)),...$ is the same as the (backward) path $v, w, p(w), p(p(w)), ... $unless $v$ lies on $Q$.
Thus if repetition occurs on $P$, then vertexto be repeated $v$ as $Q$ has no repeated vertices.
answered Dec 3 '18 at 12:48
ʎpoqouʎpoqou
3101211
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2989817%2fmodification-of-fords-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Answering my own question following the posting of solutions...
We only need to show that if $(G, c)$ contains a negative cycle, then the modified algorithm finds it.
We use induction on iteration $q$.
Case $q = 1$ is trivial.
Assume no negative cycle has been found up to (and including) iteration $q − 1$, and on iteration $q$ arc $wv$ was corrected, so $p(v) = w$. On the (backward) path $Q = w,p(w),p(p(w)),...$ there is no repetion (by induction) so its last element is $r$. The path $P = v,p(v),p(p(v)),...$ is the same as the (backward) path $v, w, p(w), p(p(w)), ... $unless $v$ lies on $Q$.
Thus if repetition occurs on $P$, then vertexto be repeated $v$ as $Q$ has no repeated vertices.
answered Dec 3 '18 at 12:48
ʎpoqouʎpoqou
3101211
$endgroup$
add a comment |
$begingroup$
Answering my own question following the posting of solutions...
We only need to show that if $(G, c)$ contains a negative cycle, then the modified algorithm finds it.
We use induction on iteration $q$.
Case $q = 1$ is trivial.
Assume no negative cycle has been found up to (and including) iteration $q − 1$, and on iteration $q$ arc $wv$ was corrected, so $p(v) = w$. On the (backward) path $Q = w,p(w),p(p(w)),...$ there is no repetion (by induction) so its last element is $r$. The path $P = v,p(v),p(p(v)),...$ is the same as the (backward) path $v, w, p(w), p(p(w)), ... $unless $v$ lies on $Q$.
Thus if repetition occurs on $P$, then vertexto be repeated $v$ as $Q$ has no repeated vertices.
answered Dec 3 '18 at 12:48
ʎpoqouʎpoqou
3101211
$endgroup$
add a comment |
$begingroup$
Answering my own question following the posting of solutions...
We only need to show that if $(G, c)$ contains a negative cycle, then the modified algorithm finds it.
We use induction on iteration $q$.
Case $q = 1$ is trivial.
Assume no negative cycle has been found up to (and including) iteration $q − 1$, and on iteration $q$ arc $wv$ was corrected, so $p(v) = w$. On the (backward) path $Q = w,p(w),p(p(w)),...$ there is no repetion (by induction) so its last element is $r$. The path $P = v,p(v),p(p(v)),...$ is the same as the (backward) path $v, w, p(w), p(p(w)), ... $unless $v$ lies on $Q$.
Thus if repetition occurs on $P$, then vertexto be repeated $v$ as $Q$ has no repeated vertices.
answered Dec 3 '18 at 12:48
ʎpoqouʎpoqou
3101211
$endgroup$
Answering my own question following the posting of solutions...
We only need to show that if $(G, c)$ contains a negative cycle, then the modified algorithm finds it.
We use induction on iteration $q$.
Case $q = 1$ is trivial.
Assume no negative cycle has been found up to (and including) iteration $q − 1$, and on iteration $q$ arc $wv$ was corrected, so $p(v) = w$. On the (backward) path $Q = w,p(w),p(p(w)),...$ there is no repetion (by induction) so its last element is $r$. The path $P = v,p(v),p(p(v)),...$ is the same as the (backward) path $v, w, p(w), p(p(w)), ... $unless $v$ lies on $Q$.
Thus if repetition occurs on $P$, then vertexto be repeated $v$ as $Q$ has no repeated vertices.
answered Dec 3 '18 at 12:48
ʎpoqouʎpoqou
3101211
answered Dec 3 '18 at 12:48
ʎpoqouʎpoqou
3101211
answered Dec 3 '18 at 12:48
ʎpoqouʎpoqou
3101211
answered Dec 3 '18 at 12:48
ʎpoqouʎpoqou
3101211
3101211
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2989817%2fmodification-of-fords-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
To get the ball rolling... On the first iteration where a repeated element is detected in the sequence $w,p(w),p(p(w)),...$ the repeated element has to be $w$. Otherwise the sequence $p(w),p(p(w)),...$ that was encountered on a previous iteration would contain a repeated element. Either the root $r$ is the last element of sequence $w,p(w),p(p(w)),...$ or $w$ appears in that sequence again.
$endgroup$
– ʎpoqou
Nov 8 '18 at 14:54