0
$\begingroup$

If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained by BFS. Here, i consider that each weight of the edge is the minimum of the end vertices and the weight of the path is the sum of the edges weights divided by the number of edges on the path. I am unable to use BFS for such algoritm. Please suggest me a suitable known algorithm to solve such problem. I would also prefer to know if i can use suitable programming codes in C++ to solve such problem? The following problem is solved manually, but i wish to solve it by using some known algorithm or, programming codes. I am new to C programming as well as to this site, so if my question off-topic, then please refer me an appropriate site. Thank you, enter image description here

Note 1 The above problem is solved just manually. Instead, i want to use suitable known algorithm or programming codes in C++ to solve this problem. I have just installed Dev-C++ to try. Note 2 Here, the graph $G$ is complete (except the edge $(0, 6)$ being removed) having $0$ as the source vertex and $6$ as the target vertex.

Improve this question
$\endgroup$
5
  • $\begingroup$ For weighted graphs Dijkstra's algorithm is the place to start. $\endgroup$
    – Richard
    Commented Apr 25, 2019 at 16:43
  • $\begingroup$ Can you please write down the source of your picture? $\endgroup$
    – Encipher
    Commented Apr 26, 2019 at 2:30
  • $\begingroup$ A variant of Dijkstra’s algorithm should be great algorithm to start with as @Richard suggested, particularly since your weights are non-negative from the sound of it. That said, you can certainly model this more generically using dynamic programming and that may be the way to go if you cannot massage Dijkstra’s algorithm to work with your path cost situation. $\endgroup$
    – spektr
    Commented Apr 26, 2019 at 5:30
  • $\begingroup$ @spektr Would you kindly help me to write codes in Dynamic programming or Dikstra's algorithm to fix my problem? I am not acquainted with such codes. $\endgroup$
    – gete
    Commented Apr 26, 2019 at 11:34
  • $\begingroup$ @Encipher The picture i have drawn here is a weighted complete graph (except the source $0$ and the target $6$ has no direct edge) . How can i find the shortest path between these two nodes using programming codes in C++? $\endgroup$
    – gete
    Commented Apr 26, 2019 at 11:39

1 Answer 1

Reset to default
3
$\begingroup$

Based on the provided description as well as the figure, you have an undirected graph with a single source and a sink at hand. The most famous option is to implement Dijkstra's algorithm. There are other options that are faster, but as long as your dealing with small instances and have no CPU time limit, I think you're good to go. In case you're interested, Wikipedia has a list of some other option, available from here.

As for the implementation, there are lots of available code on the web (some example are available from here and here, but you might find other implementations as well). In addition, if you're interested in learning how to code these kinds of algorithms, a good start point is to study the pseudo-code of your chosen algorithm (for the pseudo-code of Dijkstra's algorithm, see here).

ps. In case you need to find the shortest paths between all pairs of nodes, you might try using Floyd–Warshall algorithm.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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