Styjun

How did Biff return to 2015 from 1955 without a lightning strike?

How to structure presentation to avoid getting questions that will be answered later in the presentation?

"Will flex for food". What does this phrase mean?

Why do player start with fighting for the corners in go?

Applying for mortgage when living together but only one will be on the mortgage

How does Asimov's second law deal with contradictory orders from different people?

How to avoid a lengthy conversation with someone from the neighborhood I don't share interests with

Traveling from New York city to Starkville Mississippi with public transport

Is Illustrator accurate for business card sizes?

Is Norway in the Single Market?

Export economy of Mars

How can a class have multiple methods without breaking the single responsibility principle

Is it moral to remove/hide certain parts of a photo, as a photographer?

Is this popular optical illusion made of a grey-scale image with coloured lines?

Can living where (rare) earth magnetic ore is abundant provide any protection from cosmic radiation?

If a Shadow Magic sorcerer casts Darkness using the Eyes of the Dark feature, can they cast another spell that requires concentration?

Checking whether the win-loss standings of a league are possible

How do I respond appropriately to an overseas company that obtained a visa for me without hiring me?

Can an alphabet for a Turing machine contain subsets of other alphabets?

Gold Battle KoTH

What is the difference between "logical equivalence" and "material equivalence"?

How do people drown while wearing a life jacket?

UX writing: When to use "we"?

Need help in optimizing the below helper class

Find min cost from node A to node B and also keep the path info

What is the difference between tree depth and height?Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missingFinding the shortest path in a graph between 2 nodes that goes through a subset of nodesModifying shortest path to get a min-cost pathImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionFinding cheapest path on a graph, cost determined by max-weight of used nodesAlgorithm for finding cost of a node based on preceding nodes in a cyclic graphfinding shortest path in a weighted graphModified Dijkstra's AlgorithmIssue with min cost path

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

0

I got a question which is to find the min cost from the least number node (1) to the largest number node (7).

The cost is the edge between nodes. I labeled them.

This problem got me to think of the Dijkstra which leads the time complexity for O((v+e) log v)

Any other better approach to solving this question efficiently?

The other requirement is to keep the path information, any thought to keep the path?

algorithm

share|improve this question

edited Mar 27 at 6:16

newBike

asked Mar 27 at 0:26

newBikenewBike

4,7391818 gold badges6464 silver badges128128 bronze badges

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  This is exactly what Dijkstra's algorithm is for. If it weren't the best way, you would know. :-)
  
  – ruakh
  Mar 27 at 0:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Bidirectional Dijkstra might be faster in practice since you reduce the number of nodes to visit. It has the same theoretical complexity, though.
  
  – Nico Schertler
  Mar 27 at 3:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  bfs algorithm would help
  
  – prashant rana
  Mar 27 at 4:26
  

  
  
  
  

add a comment | 

0

I got a question which is to find the min cost from the least number node (1) to the largest number node (7).

The cost is the edge between nodes. I labeled them.

This problem got me to think of the Dijkstra which leads the time complexity for O((v+e) log v)

Any other better approach to solving this question efficiently?

The other requirement is to keep the path information, any thought to keep the path?

algorithm

share|improve this question

edited Mar 27 at 6:16

newBike

asked Mar 27 at 0:26

newBikenewBike

4,7391818 gold badges6464 silver badges128128 bronze badges

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  This is exactly what Dijkstra's algorithm is for. If it weren't the best way, you would know. :-)
  
  – ruakh
  Mar 27 at 0:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Bidirectional Dijkstra might be faster in practice since you reduce the number of nodes to visit. It has the same theoretical complexity, though.
  
  – Nico Schertler
  Mar 27 at 3:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  bfs algorithm would help
  
  – prashant rana
  Mar 27 at 4:26
  

  
  
  
  

add a comment | 

I got a question which is to find the min cost from the least number node (1) to the largest number node (7).

The cost is the edge between nodes. I labeled them.

This problem got me to think of the Dijkstra which leads the time complexity for O((v+e) log v)

Any other better approach to solving this question efficiently?

The other requirement is to keep the path information, any thought to keep the path?

algorithm

share|improve this question

edited Mar 27 at 6:16

newBike

asked Mar 27 at 0:26

newBikenewBike

4,7391818 gold badges6464 silver badges128128 bronze badges

share|improve this question

edited Mar 27 at 6:16

newBike

asked Mar 27 at 0:26

newBikenewBike

4,7391818 gold badges6464 silver badges128128 bronze badges

share|improve this question

edited Mar 27 at 6:16

newBike

asked Mar 27 at 0:26

newBikenewBike

4,7391818 gold badges6464 silver badges128128 bronze badges

asked Mar 27 at 0:26

newBikenewBike

4,7391818 gold badges6464 silver badges128128 bronze badges

asked Mar 27 at 0:26

newBikenewBike

4,7391818 gold badges6464 silver badges128128 bronze badges

1 Answer
1

active

oldest

votes

1

As others pointed out, the complexity is as you say and cannot be better. As @nico-schertler commented, searching from both sides in parallel (or taking turns) and stopping as soon as something touches is faster than doing just a search from one side, but it will have the same complexity. It is possible in this case (with fixed costs for the bidirectional edges) but it needs not be in the general case (e. g. cost depending on the already taken path) where Dijkstra is still applicable.

Concerning the keeping of the path: Of course, the whole thing often only makes sense if you get the path to be taken as an answer. There are two main approaches to get the path as a result.

One is to store the path already taken to a certain node along with the node in the lists (white/grey in the classical implementation). Each time you add a new node, you extend the path of its former node by one step. If you find the target node, you can directly return the path as a result (along with the cost sum). Of course this way means uses a lot of memory.

The other is to not store the origin node along with each new found node, so each node points to the node it was visited from first. Think of it as putting up signposts in each node how to go back. This way, if you find the target node, you will have to go backwards from each node to the one it was first visited from and build the path in reverse order in the process. Then you can return this path.

share|improve this answer

edited Mar 27 at 16:07

answered Mar 27 at 14:43

AlfeAlfe

34.8k1212 gold badges6767 silver badges120120 bronze badges

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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55368074%2ffind-min-cost-from-node-a-to-node-b-and-also-keep-the-path-info%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

As others pointed out, the complexity is as you say and cannot be better. As @nico-schertler commented, searching from both sides in parallel (or taking turns) and stopping as soon as something touches is faster than doing just a search from one side, but it will have the same complexity. It is possible in this case (with fixed costs for the bidirectional edges) but it needs not be in the general case (e. g. cost depending on the already taken path) where Dijkstra is still applicable.

Concerning the keeping of the path: Of course, the whole thing often only makes sense if you get the path to be taken as an answer. There are two main approaches to get the path as a result.

One is to store the path already taken to a certain node along with the node in the lists (white/grey in the classical implementation). Each time you add a new node, you extend the path of its former node by one step. If you find the target node, you can directly return the path as a result (along with the cost sum). Of course this way means uses a lot of memory.

The other is to not store the origin node along with each new found node, so each node points to the node it was visited from first. Think of it as putting up signposts in each node how to go back. This way, if you find the target node, you will have to go backwards from each node to the one it was first visited from and build the path in reverse order in the process. Then you can return this path.

share|improve this answer

edited Mar 27 at 16:07

answered Mar 27 at 14:43

AlfeAlfe

34.8k1212 gold badges6767 silver badges120120 bronze badges

add a comment | 

1

As others pointed out, the complexity is as you say and cannot be better. As @nico-schertler commented, searching from both sides in parallel (or taking turns) and stopping as soon as something touches is faster than doing just a search from one side, but it will have the same complexity. It is possible in this case (with fixed costs for the bidirectional edges) but it needs not be in the general case (e. g. cost depending on the already taken path) where Dijkstra is still applicable.

Concerning the keeping of the path: Of course, the whole thing often only makes sense if you get the path to be taken as an answer. There are two main approaches to get the path as a result.

One is to store the path already taken to a certain node along with the node in the lists (white/grey in the classical implementation). Each time you add a new node, you extend the path of its former node by one step. If you find the target node, you can directly return the path as a result (along with the cost sum). Of course this way means uses a lot of memory.

The other is to not store the origin node along with each new found node, so each node points to the node it was visited from first. Think of it as putting up signposts in each node how to go back. This way, if you find the target node, you will have to go backwards from each node to the one it was first visited from and build the path in reverse order in the process. Then you can return this path.

share|improve this answer

edited Mar 27 at 16:07

answered Mar 27 at 14:43

AlfeAlfe

34.8k1212 gold badges6767 silver badges120120 bronze badges

add a comment | 

As others pointed out, the complexity is as you say and cannot be better. As @nico-schertler commented, searching from both sides in parallel (or taking turns) and stopping as soon as something touches is faster than doing just a search from one side, but it will have the same complexity. It is possible in this case (with fixed costs for the bidirectional edges) but it needs not be in the general case (e. g. cost depending on the already taken path) where Dijkstra is still applicable.

Concerning the keeping of the path: Of course, the whole thing often only makes sense if you get the path to be taken as an answer. There are two main approaches to get the path as a result.

One is to store the path already taken to a certain node along with the node in the lists (white/grey in the classical implementation). Each time you add a new node, you extend the path of its former node by one step. If you find the target node, you can directly return the path as a result (along with the cost sum). Of course this way means uses a lot of memory.

The other is to not store the origin node along with each new found node, so each node points to the node it was visited from first. Think of it as putting up signposts in each node how to go back. This way, if you find the target node, you will have to go backwards from each node to the one it was first visited from and build the path in reverse order in the process. Then you can return this path.

share|improve this answer

edited Mar 27 at 16:07

answered Mar 27 at 14:43

AlfeAlfe

34.8k1212 gold badges6767 silver badges120120 bronze badges

share|improve this answer

edited Mar 27 at 16:07

answered Mar 27 at 14:43

AlfeAlfe

34.8k1212 gold badges6767 silver badges120120 bronze badges

answered Mar 27 at 14:43

AlfeAlfe

34.8k1212 gold badges6767 silver badges120120 bronze badges

answered Mar 27 at 14:43

AlfeAlfe

34.8k1212 gold badges6767 silver badges120120 bronze badges