Can anyone tell why my algorithm is wrong?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I was working on single source shortest path problem and I made a modification to bfs that can solve the problem. The algorithm runs in O(2E) times, I just can't understand why it is wrong (it must be otherwise dijstra's would not be most efficient algorithm).
def bfs_modified(G,src,des):
intialize d(src)=0, and d(!src) = inf
visited[all_vertex]=False
q=queue(src)
while q is not empty:
u=q.pop()
if(not visited[u]):
visited[u]=True
for all v connected to u:
q.insert(v)
if(d[v]>d[u]+adj[u][v]):
d[v]=d[u]+adj[u][v]
return d[des]
algorithm shortest-path
asked Jan 4 at 3:04
ASHUTOSH CHANDRAASHUTOSH CHANDRA
11911
add a comment |
I was working on single source shortest path problem and I made a modification to bfs that can solve the problem. The algorithm runs in O(2E) times, I just can't understand why it is wrong (it must be otherwise dijstra's would not be most efficient algorithm).
def bfs_modified(G,src,des):
intialize d(src)=0, and d(!src) = inf
visited[all_vertex]=False
q=queue(src)
while q is not empty:
u=q.pop()
if(not visited[u]):
visited[u]=True
for all v connected to u:
q.insert(v)
if(d[v]>d[u]+adj[u][v]):
d[v]=d[u]+adj[u][v]
return d[des]
algorithm shortest-path
asked Jan 4 at 3:04
ASHUTOSH CHANDRAASHUTOSH CHANDRA
11911
add a comment |
I was working on single source shortest path problem and I made a modification to bfs that can solve the problem. The algorithm runs in O(2E) times, I just can't understand why it is wrong (it must be otherwise dijstra's would not be most efficient algorithm).
def bfs_modified(G,src,des):
intialize d(src)=0, and d(!src) = inf
visited[all_vertex]=False
q=queue(src)
while q is not empty:
u=q.pop()
if(not visited[u]):
visited[u]=True
for all v connected to u:
q.insert(v)
if(d[v]>d[u]+adj[u][v]):
d[v]=d[u]+adj[u][v]
return d[des]
algorithm shortest-path
asked Jan 4 at 3:04
ASHUTOSH CHANDRAASHUTOSH CHANDRA
11911
I was working on single source shortest path problem and I made a modification to bfs that can solve the problem. The algorithm runs in O(2E) times, I just can't understand why it is wrong (it must be otherwise dijstra's would not be most efficient algorithm).
def bfs_modified(G,src,des):
intialize d(src)=0, and d(!src) = inf
visited[all_vertex]=False
q=queue(src)
while q is not empty:
u=q.pop()
if(not visited[u]):
visited[u]=True
for all v connected to u:
q.insert(v)
if(d[v]>d[u]+adj[u][v]):
d[v]=d[u]+adj[u][v]
return d[des]
algorithm shortest-path
algorithm shortest-path
asked Jan 4 at 3:04
ASHUTOSH CHANDRAASHUTOSH CHANDRA
11911
asked Jan 4 at 3:04
ASHUTOSH CHANDRAASHUTOSH CHANDRA
11911
asked Jan 4 at 3:04
ASHUTOSH CHANDRAASHUTOSH CHANDRA
11911
asked Jan 4 at 3:04
ASHUTOSH CHANDRAASHUTOSH CHANDRA
11911
asked Jan 4 at 3:04
ASHUTOSH CHANDRAASHUTOSH CHANDRA
11911
11911
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
In Dijkstra's algorithm, the priority queue ensures that you don't process a vertex until you know it's distance from the source.
BFS doesn't have this property. If the shortest path to a vertex has more than edges than the path with the fewest edges, then it will be processed too early.
Consider this graph, for example, when you want the shortest path from S to T:
S--5--C--1--T
| |
1 1
| |
A--1--B
Vertex C will be visited before vertex B. You will think the distance to C is 5, because you haven't discovered the shorter path. When C is visited, it will assign a distance of 6 to T. This is incorrect, and will never be fixed, because C will not be visited again.
answered Jan 4 at 3:51
Matt TimmermansMatt Timmermans
21.4k11734
yea right ! thanks!!
– ASHUTOSH CHANDRA
Jan 4 at 4:42
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%2f54032633%2fcan-anyone-tell-why-my-algorithm-is-wrong%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
In Dijkstra's algorithm, the priority queue ensures that you don't process a vertex until you know it's distance from the source.
BFS doesn't have this property. If the shortest path to a vertex has more than edges than the path with the fewest edges, then it will be processed too early.
Consider this graph, for example, when you want the shortest path from S to T:
S--5--C--1--T
| |
1 1
| |
A--1--B
Vertex C will be visited before vertex B. You will think the distance to C is 5, because you haven't discovered the shorter path. When C is visited, it will assign a distance of 6 to T. This is incorrect, and will never be fixed, because C will not be visited again.
answered Jan 4 at 3:51
Matt TimmermansMatt Timmermans
21.4k11734
yea right ! thanks!!
– ASHUTOSH CHANDRA
Jan 4 at 4:42
add a comment |
In Dijkstra's algorithm, the priority queue ensures that you don't process a vertex until you know it's distance from the source.
BFS doesn't have this property. If the shortest path to a vertex has more than edges than the path with the fewest edges, then it will be processed too early.
Consider this graph, for example, when you want the shortest path from S to T:
S--5--C--1--T
| |
1 1
| |
A--1--B
Vertex C will be visited before vertex B. You will think the distance to C is 5, because you haven't discovered the shorter path. When C is visited, it will assign a distance of 6 to T. This is incorrect, and will never be fixed, because C will not be visited again.
answered Jan 4 at 3:51
Matt TimmermansMatt Timmermans
21.4k11734
yea right ! thanks!!
– ASHUTOSH CHANDRA
Jan 4 at 4:42
add a comment |
In Dijkstra's algorithm, the priority queue ensures that you don't process a vertex until you know it's distance from the source.
BFS doesn't have this property. If the shortest path to a vertex has more than edges than the path with the fewest edges, then it will be processed too early.
Consider this graph, for example, when you want the shortest path from S to T:
S--5--C--1--T
| |
1 1
| |
A--1--B
Vertex C will be visited before vertex B. You will think the distance to C is 5, because you haven't discovered the shorter path. When C is visited, it will assign a distance of 6 to T. This is incorrect, and will never be fixed, because C will not be visited again.
answered Jan 4 at 3:51
Matt TimmermansMatt Timmermans
21.4k11734
In Dijkstra's algorithm, the priority queue ensures that you don't process a vertex until you know it's distance from the source.
BFS doesn't have this property. If the shortest path to a vertex has more than edges than the path with the fewest edges, then it will be processed too early.
Consider this graph, for example, when you want the shortest path from S to T:
S--5--C--1--T
| |
1 1
| |
A--1--B
Vertex C will be visited before vertex B. You will think the distance to C is 5, because you haven't discovered the shorter path. When C is visited, it will assign a distance of 6 to T. This is incorrect, and will never be fixed, because C will not be visited again.
answered Jan 4 at 3:51
Matt TimmermansMatt Timmermans
21.4k11734
answered Jan 4 at 3:51
Matt TimmermansMatt Timmermans
21.4k11734
answered Jan 4 at 3:51
Matt TimmermansMatt Timmermans
21.4k11734
answered Jan 4 at 3:51
Matt TimmermansMatt Timmermans
21.4k11734
21.4k11734
yea right ! thanks!!
– ASHUTOSH CHANDRA
Jan 4 at 4:42
add a comment |
yea right ! thanks!!
– ASHUTOSH CHANDRA
Jan 4 at 4:42
yea right ! thanks!!
– ASHUTOSH CHANDRA
Jan 4 at 4:42
yea right ! thanks!!
– ASHUTOSH CHANDRA
Jan 4 at 4:42
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%2f54032633%2fcan-anyone-tell-why-my-algorithm-is-wrong%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
