How to find a path in graph with maximum edges?

How can i find shortest path without graph theory?

• i have to write a c++ algorithm to find the shortest path of a graph. but we are not allowed to use graph theory algorithms such as Dijkstra's algorithm, etc. We were thinking ...show more

• Answer:

  Use the unweighted breadth-first traversal algorithm. It basically assigns a weight to each edge, starting at any vertex. Then run the algorithm on the graph with a specify vertex and it will give you the shortest path to that vertex. The lowest weight is the shortest path. Here are some sources that will help you out: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L21-MinPath.htm http://www.ecs.umass.edu/~mettu/ece242/lectures/Unit%20Weight%20Shortest%20Paths%20and%20Spanning%20Trees.pdf (page 8-10)