-1
$\begingroup$

I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.

$\endgroup$
2
  • 1
    $\begingroup$ I think you'll need to edit your question to elaborate. Our site works differently from other sites you might be used to (like Quora), and our expectations are different. You might want to look at some other questions to get an idea for how things work here. Please state the question in the body. The title should be a short summary, not the question. Please define what you mean by "find the best cost". I suggest you list the inputs to the algorithm and specify the desired output. $\endgroup$
    – D.W.
    Aug 7 at 16:53
  • $\begingroup$ (If it was a directed graph, it should be possible to add each vertex' cost to every incoming edge and set to zero/ignore thereafter.) $\endgroup$
    – greybeard
    Aug 7 at 17:23

1 Answer 1

0
$\begingroup$

One solution would be to convert the original graph to a graph with only edge costs, and then use Dijkstra's algorithm.

To do this we can replace a single node with n nodes which are fully connected to each other. n is the number of edges entering that node.

enter image description here

Note: This solution assumes that weights are non negative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.