Minimum Weighted Path Tree of an Undirected Graph
Assume that we have an undirected graph G=(V,E) and we have two nodes S and X.
- Can we come up with an algorithm such that the largest weight of the edge on the path from S to X is minimized? Note that it is not the shortest path algorithm since we are not interested in minimizing their sum.
- What is the complexity of this algorithm?
- Is the minimum spanning tree algorithm (such as Prim) is a solution for the problem?
algorithm tree graph-theory
edited Nov 15 '18 at 4:26
Dominique Fortin
1,648816
asked Nov 14 '18 at 16:00
kemal4488kemal4488
12
add a comment |
Assume that we have an undirected graph G=(V,E) and we have two nodes S and X.
- Can we come up with an algorithm such that the largest weight of the edge on the path from S to X is minimized? Note that it is not the shortest path algorithm since we are not interested in minimizing their sum.
- What is the complexity of this algorithm?
- Is the minimum spanning tree algorithm (such as Prim) is a solution for the problem?
algorithm tree graph-theory
edited Nov 15 '18 at 4:26
Dominique Fortin
1,648816
asked Nov 14 '18 at 16:00
kemal4488kemal4488
12
add a comment |
Assume that we have an undirected graph G=(V,E) and we have two nodes S and X.
- Can we come up with an algorithm such that the largest weight of the edge on the path from S to X is minimized? Note that it is not the shortest path algorithm since we are not interested in minimizing their sum.
- What is the complexity of this algorithm?
- Is the minimum spanning tree algorithm (such as Prim) is a solution for the problem?
algorithm tree graph-theory
edited Nov 15 '18 at 4:26
Dominique Fortin
1,648816
asked Nov 14 '18 at 16:00
kemal4488kemal4488
12
Assume that we have an undirected graph G=(V,E) and we have two nodes S and X.
- Can we come up with an algorithm such that the largest weight of the edge on the path from S to X is minimized? Note that it is not the shortest path algorithm since we are not interested in minimizing their sum.
- What is the complexity of this algorithm?
- Is the minimum spanning tree algorithm (such as Prim) is a solution for the problem?
algorithm tree graph-theory
algorithm tree graph-theory
edited Nov 15 '18 at 4:26
Dominique Fortin
1,648816
asked Nov 14 '18 at 16:00
kemal4488kemal4488
12
edited Nov 15 '18 at 4:26
Dominique Fortin
1,648816
asked Nov 14 '18 at 16:00
kemal4488kemal4488
12
edited Nov 15 '18 at 4:26
Dominique Fortin
1,648816
edited Nov 15 '18 at 4:26
Dominique Fortin
1,648816
edited Nov 15 '18 at 4:26
Dominique Fortin
1,648816
1,648816
asked Nov 14 '18 at 16:00
kemal4488kemal4488
12
asked Nov 14 '18 at 16:00
kemal4488kemal4488
12
asked Nov 14 '18 at 16:00
kemal4488kemal4488
12
12
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
I don't know if minimum spanning tree will solve it or not, but it's certainly solvable by making some modifications to Dijkstra's algorithm.
Define the "length" of a path as the maximum edge in that path. Now find the shortest path from S to X using Dijkstra's algorithm. This is the path you are looking for.
Complexity is O((N+M)log N) if you use a binary heap and O(N * log N + M) with a Fibonacci heap.
Note that for this new definition of path length, if the length of a path is l, then adding an edge to the end of the path will not decrease it's length, since the maximum edge in that path can only increase. This property is necessary for Dijkstra's algorithm to work correctly.
For instance, if you were looking for the path with the shortest edge, then Dijkstra's algorithm will fail just like it fails when there are negative edges in the graph.
answered Nov 14 '18 at 16:44
merlynmerlyn
1,73011222
Now think of a graph V=(V1,v2,v3) and E=((v1,v2,2),(v2,v3,2),(v1,v3,3)). Let S=v2 and X=v3. Dijkstra will return (v1,v3) with shortest path of 3 in total but the answer is (v1,v2) and (v2,v3) with a path of 4, which consists 2 edges with weights of 2. So in this problem, we expect the latter. Could you explain please that the modified Dijkstra algorithm that you offer gives the correct answer?
– kemal4488
Nov 14 '18 at 16:56
@kemal4488 I think you meant S=v1. Anyways, normal Dijkstra will return shortest path as 3, but the new Dijkstra where you measure the maximum edge will provide 2. Here's how it goes. You look at adjacent nodes from v1. v2 is at distance 2 & v3 is at distance 3. We take the closest v2. v2 has a neighbor v3 at dist 2. Now, in normal Dijkstra the new distance would be 2 + 2. But, in our Dijkstra, the new distance is max(2, 2). Since max(2, 2) is less than v3's original distance 3, we update it. You see how you get the correct answer in the end?
– merlyn
Nov 14 '18 at 17:04
Yes, in the example S=v1 and X=v3. I now understand what you have meant. Thank you.
– kemal4488
Nov 14 '18 at 17:22
add a comment |
You can use minimum spanning tree (Prim's algorithm) to solve this problem. You will start with vertex S, then continue to build the tree using Prim's algorithm until you find X. Complexity will be O((V+E)*logV).
It will work because in the prim's algorithm you always choose the edge with minimum weight first.
answered Nov 14 '18 at 17:06
nightfury1204nightfury1204
1,68449
Today, it was a part of the question in my proficiency exam and your answer is exactly what I did. I hope (and believe) this is a solution alternative. Thank you.
– kemal4488
Nov 14 '18 at 17:26
@kemal4488 if you look at the merlyn answer and prim's algorithm they actually are closely related.
– nightfury1204
Nov 14 '18 at 17:31
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f53304245%2fminimum-weighted-path-tree-of-an-undirected-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
I don't know if minimum spanning tree will solve it or not, but it's certainly solvable by making some modifications to Dijkstra's algorithm.
Define the "length" of a path as the maximum edge in that path. Now find the shortest path from S to X using Dijkstra's algorithm. This is the path you are looking for.
Complexity is O((N+M)log N) if you use a binary heap and O(N * log N + M) with a Fibonacci heap.
Note that for this new definition of path length, if the length of a path is l, then adding an edge to the end of the path will not decrease it's length, since the maximum edge in that path can only increase. This property is necessary for Dijkstra's algorithm to work correctly.
For instance, if you were looking for the path with the shortest edge, then Dijkstra's algorithm will fail just like it fails when there are negative edges in the graph.
answered Nov 14 '18 at 16:44
merlynmerlyn
1,73011222
Now think of a graph V=(V1,v2,v3) and E=((v1,v2,2),(v2,v3,2),(v1,v3,3)). Let S=v2 and X=v3. Dijkstra will return (v1,v3) with shortest path of 3 in total but the answer is (v1,v2) and (v2,v3) with a path of 4, which consists 2 edges with weights of 2. So in this problem, we expect the latter. Could you explain please that the modified Dijkstra algorithm that you offer gives the correct answer?
– kemal4488
Nov 14 '18 at 16:56
@kemal4488 I think you meant S=v1. Anyways, normal Dijkstra will return shortest path as 3, but the new Dijkstra where you measure the maximum edge will provide 2. Here's how it goes. You look at adjacent nodes from v1. v2 is at distance 2 & v3 is at distance 3. We take the closest v2. v2 has a neighbor v3 at dist 2. Now, in normal Dijkstra the new distance would be 2 + 2. But, in our Dijkstra, the new distance is max(2, 2). Since max(2, 2) is less than v3's original distance 3, we update it. You see how you get the correct answer in the end?
– merlyn
Nov 14 '18 at 17:04
Yes, in the example S=v1 and X=v3. I now understand what you have meant. Thank you.
– kemal4488
Nov 14 '18 at 17:22
add a comment |
I don't know if minimum spanning tree will solve it or not, but it's certainly solvable by making some modifications to Dijkstra's algorithm.
Define the "length" of a path as the maximum edge in that path. Now find the shortest path from S to X using Dijkstra's algorithm. This is the path you are looking for.
Complexity is O((N+M)log N) if you use a binary heap and O(N * log N + M) with a Fibonacci heap.
Note that for this new definition of path length, if the length of a path is l, then adding an edge to the end of the path will not decrease it's length, since the maximum edge in that path can only increase. This property is necessary for Dijkstra's algorithm to work correctly.
For instance, if you were looking for the path with the shortest edge, then Dijkstra's algorithm will fail just like it fails when there are negative edges in the graph.
answered Nov 14 '18 at 16:44
merlynmerlyn
1,73011222
Now think of a graph V=(V1,v2,v3) and E=((v1,v2,2),(v2,v3,2),(v1,v3,3)). Let S=v2 and X=v3. Dijkstra will return (v1,v3) with shortest path of 3 in total but the answer is (v1,v2) and (v2,v3) with a path of 4, which consists 2 edges with weights of 2. So in this problem, we expect the latter. Could you explain please that the modified Dijkstra algorithm that you offer gives the correct answer?
– kemal4488
Nov 14 '18 at 16:56
@kemal4488 I think you meant S=v1. Anyways, normal Dijkstra will return shortest path as 3, but the new Dijkstra where you measure the maximum edge will provide 2. Here's how it goes. You look at adjacent nodes from v1. v2 is at distance 2 & v3 is at distance 3. We take the closest v2. v2 has a neighbor v3 at dist 2. Now, in normal Dijkstra the new distance would be 2 + 2. But, in our Dijkstra, the new distance is max(2, 2). Since max(2, 2) is less than v3's original distance 3, we update it. You see how you get the correct answer in the end?
– merlyn
Nov 14 '18 at 17:04
Yes, in the example S=v1 and X=v3. I now understand what you have meant. Thank you.
– kemal4488
Nov 14 '18 at 17:22
add a comment |
I don't know if minimum spanning tree will solve it or not, but it's certainly solvable by making some modifications to Dijkstra's algorithm.
Define the "length" of a path as the maximum edge in that path. Now find the shortest path from S to X using Dijkstra's algorithm. This is the path you are looking for.
Complexity is O((N+M)log N) if you use a binary heap and O(N * log N + M) with a Fibonacci heap.
Note that for this new definition of path length, if the length of a path is l, then adding an edge to the end of the path will not decrease it's length, since the maximum edge in that path can only increase. This property is necessary for Dijkstra's algorithm to work correctly.
For instance, if you were looking for the path with the shortest edge, then Dijkstra's algorithm will fail just like it fails when there are negative edges in the graph.
answered Nov 14 '18 at 16:44
merlynmerlyn
1,73011222
I don't know if minimum spanning tree will solve it or not, but it's certainly solvable by making some modifications to Dijkstra's algorithm.
Define the "length" of a path as the maximum edge in that path. Now find the shortest path from S to X using Dijkstra's algorithm. This is the path you are looking for.
Complexity is O((N+M)log N) if you use a binary heap and O(N * log N + M) with a Fibonacci heap.
Note that for this new definition of path length, if the length of a path is l, then adding an edge to the end of the path will not decrease it's length, since the maximum edge in that path can only increase. This property is necessary for Dijkstra's algorithm to work correctly.
For instance, if you were looking for the path with the shortest edge, then Dijkstra's algorithm will fail just like it fails when there are negative edges in the graph.
answered Nov 14 '18 at 16:44
merlynmerlyn
1,73011222
answered Nov 14 '18 at 16:44
merlynmerlyn
1,73011222
answered Nov 14 '18 at 16:44
merlynmerlyn
1,73011222
answered Nov 14 '18 at 16:44
merlynmerlyn
1,73011222
1,73011222
Now think of a graph V=(V1,v2,v3) and E=((v1,v2,2),(v2,v3,2),(v1,v3,3)). Let S=v2 and X=v3. Dijkstra will return (v1,v3) with shortest path of 3 in total but the answer is (v1,v2) and (v2,v3) with a path of 4, which consists 2 edges with weights of 2. So in this problem, we expect the latter. Could you explain please that the modified Dijkstra algorithm that you offer gives the correct answer?
– kemal4488
Nov 14 '18 at 16:56
@kemal4488 I think you meant S=v1. Anyways, normal Dijkstra will return shortest path as 3, but the new Dijkstra where you measure the maximum edge will provide 2. Here's how it goes. You look at adjacent nodes from v1. v2 is at distance 2 & v3 is at distance 3. We take the closest v2. v2 has a neighbor v3 at dist 2. Now, in normal Dijkstra the new distance would be 2 + 2. But, in our Dijkstra, the new distance is max(2, 2). Since max(2, 2) is less than v3's original distance 3, we update it. You see how you get the correct answer in the end?
– merlyn
Nov 14 '18 at 17:04
Yes, in the example S=v1 and X=v3. I now understand what you have meant. Thank you.
– kemal4488
Nov 14 '18 at 17:22
add a comment |
Now think of a graph V=(V1,v2,v3) and E=((v1,v2,2),(v2,v3,2),(v1,v3,3)). Let S=v2 and X=v3. Dijkstra will return (v1,v3) with shortest path of 3 in total but the answer is (v1,v2) and (v2,v3) with a path of 4, which consists 2 edges with weights of 2. So in this problem, we expect the latter. Could you explain please that the modified Dijkstra algorithm that you offer gives the correct answer?
– kemal4488
Nov 14 '18 at 16:56
@kemal4488 I think you meant S=v1. Anyways, normal Dijkstra will return shortest path as 3, but the new Dijkstra where you measure the maximum edge will provide 2. Here's how it goes. You look at adjacent nodes from v1. v2 is at distance 2 & v3 is at distance 3. We take the closest v2. v2 has a neighbor v3 at dist 2. Now, in normal Dijkstra the new distance would be 2 + 2. But, in our Dijkstra, the new distance is max(2, 2). Since max(2, 2) is less than v3's original distance 3, we update it. You see how you get the correct answer in the end?
– merlyn
Nov 14 '18 at 17:04
Yes, in the example S=v1 and X=v3. I now understand what you have meant. Thank you.
– kemal4488
Nov 14 '18 at 17:22
Now think of a graph V=(V1,v2,v3) and E=((v1,v2,2),(v2,v3,2),(v1,v3,3)). Let S=v2 and X=v3. Dijkstra will return (v1,v3) with shortest path of 3 in total but the answer is (v1,v2) and (v2,v3) with a path of 4, which consists 2 edges with weights of 2. So in this problem, we expect the latter. Could you explain please that the modified Dijkstra algorithm that you offer gives the correct answer?
– kemal4488
Nov 14 '18 at 16:56
Now think of a graph V=(V1,v2,v3) and E=((v1,v2,2),(v2,v3,2),(v1,v3,3)). Let S=v2 and X=v3. Dijkstra will return (v1,v3) with shortest path of 3 in total but the answer is (v1,v2) and (v2,v3) with a path of 4, which consists 2 edges with weights of 2. So in this problem, we expect the latter. Could you explain please that the modified Dijkstra algorithm that you offer gives the correct answer?
– kemal4488
Nov 14 '18 at 16:56
@kemal4488 I think you meant S=v1. Anyways, normal Dijkstra will return shortest path as 3, but the new Dijkstra where you measure the maximum edge will provide 2. Here's how it goes. You look at adjacent nodes from v1. v2 is at distance 2 & v3 is at distance 3. We take the closest v2. v2 has a neighbor v3 at dist 2. Now, in normal Dijkstra the new distance would be 2 + 2. But, in our Dijkstra, the new distance is max(2, 2). Since max(2, 2) is less than v3's original distance 3, we update it. You see how you get the correct answer in the end?
– merlyn
Nov 14 '18 at 17:04
@kemal4488 I think you meant S=v1. Anyways, normal Dijkstra will return shortest path as 3, but the new Dijkstra where you measure the maximum edge will provide 2. Here's how it goes. You look at adjacent nodes from v1. v2 is at distance 2 & v3 is at distance 3. We take the closest v2. v2 has a neighbor v3 at dist 2. Now, in normal Dijkstra the new distance would be 2 + 2. But, in our Dijkstra, the new distance is max(2, 2). Since max(2, 2) is less than v3's original distance 3, we update it. You see how you get the correct answer in the end?
– merlyn
Nov 14 '18 at 17:04
Yes, in the example S=v1 and X=v3. I now understand what you have meant. Thank you.
– kemal4488
Nov 14 '18 at 17:22
Yes, in the example S=v1 and X=v3. I now understand what you have meant. Thank you.
– kemal4488
Nov 14 '18 at 17:22
add a comment |
You can use minimum spanning tree (Prim's algorithm) to solve this problem. You will start with vertex S, then continue to build the tree using Prim's algorithm until you find X. Complexity will be O((V+E)*logV).
It will work because in the prim's algorithm you always choose the edge with minimum weight first.
answered Nov 14 '18 at 17:06
nightfury1204nightfury1204
1,68449
Today, it was a part of the question in my proficiency exam and your answer is exactly what I did. I hope (and believe) this is a solution alternative. Thank you.
– kemal4488
Nov 14 '18 at 17:26
@kemal4488 if you look at the merlyn answer and prim's algorithm they actually are closely related.
– nightfury1204
Nov 14 '18 at 17:31
add a comment |
You can use minimum spanning tree (Prim's algorithm) to solve this problem. You will start with vertex S, then continue to build the tree using Prim's algorithm until you find X. Complexity will be O((V+E)*logV).
It will work because in the prim's algorithm you always choose the edge with minimum weight first.
answered Nov 14 '18 at 17:06
nightfury1204nightfury1204
1,68449
Today, it was a part of the question in my proficiency exam and your answer is exactly what I did. I hope (and believe) this is a solution alternative. Thank you.
– kemal4488
Nov 14 '18 at 17:26
@kemal4488 if you look at the merlyn answer and prim's algorithm they actually are closely related.
– nightfury1204
Nov 14 '18 at 17:31
add a comment |
You can use minimum spanning tree (Prim's algorithm) to solve this problem. You will start with vertex S, then continue to build the tree using Prim's algorithm until you find X. Complexity will be O((V+E)*logV).
It will work because in the prim's algorithm you always choose the edge with minimum weight first.
answered Nov 14 '18 at 17:06
nightfury1204nightfury1204
1,68449
You can use minimum spanning tree (Prim's algorithm) to solve this problem. You will start with vertex S, then continue to build the tree using Prim's algorithm until you find X. Complexity will be O((V+E)*logV).
It will work because in the prim's algorithm you always choose the edge with minimum weight first.
answered Nov 14 '18 at 17:06
nightfury1204nightfury1204
1,68449
answered Nov 14 '18 at 17:06
nightfury1204nightfury1204
1,68449
answered Nov 14 '18 at 17:06
nightfury1204nightfury1204
1,68449
answered Nov 14 '18 at 17:06
nightfury1204nightfury1204
1,68449
1,68449
Today, it was a part of the question in my proficiency exam and your answer is exactly what I did. I hope (and believe) this is a solution alternative. Thank you.
– kemal4488
Nov 14 '18 at 17:26
@kemal4488 if you look at the merlyn answer and prim's algorithm they actually are closely related.
– nightfury1204
Nov 14 '18 at 17:31
add a comment |
Today, it was a part of the question in my proficiency exam and your answer is exactly what I did. I hope (and believe) this is a solution alternative. Thank you.
– kemal4488
Nov 14 '18 at 17:26
@kemal4488 if you look at the merlyn answer and prim's algorithm they actually are closely related.
– nightfury1204
Nov 14 '18 at 17:31
Today, it was a part of the question in my proficiency exam and your answer is exactly what I did. I hope (and believe) this is a solution alternative. Thank you.
– kemal4488
Nov 14 '18 at 17:26
Today, it was a part of the question in my proficiency exam and your answer is exactly what I did. I hope (and believe) this is a solution alternative. Thank you.
– kemal4488
Nov 14 '18 at 17:26
@kemal4488 if you look at the merlyn answer and prim's algorithm they actually are closely related.
– nightfury1204
Nov 14 '18 at 17:31
@kemal4488 if you look at the merlyn answer and prim's algorithm they actually are closely related.
– nightfury1204
Nov 14 '18 at 17:31
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53304245%2fminimum-weighted-path-tree-of-an-undirected-graph%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
