I've written a DFS algorithm which finds a path between to vertices in a graph but want to optimize it to return the path containing the minimum number of edges.
I wanted to just switch to a BFS algorithm, but I'm unsure of how I would need to modify it given the properties of my graph and the criteria the resulting path must meet.
The Graph: Undirected, weighted and contains edges with positive weights, negative weights, and weights of 0.
The Path: Cannot visit any vertex more than once. Total weight of the path must always be positive including the path up to any vertex before the vertex of the end of the path.
The weights can be thought of as the cost to use each path and the total weight as the amount available to use. Positive weights increase the amount available to use and negative weights cost their weight to use.
Any help would be appreciated, thanks!
BFS is applicable to unweighted graphs (or graphs where all edges have the same weight).
For weighted graphs one can use algorithms such as Dijkstra's (which is a "modified BFS"), or A* (which is a "modified Dijkstra's") .
However both Dijkstra's or A* do not work correctly with negative weights.
For graph with negative weights consider
Bellman–Ford algorithm.
Edit: If you only want to use the smallest number of edges whilst maintaining
Total weight of the path must always be positive including the path up to any vertex before the vertex of the end of the path.
you can use BFS and use the weight just as selection criteria, meaning check before adding an edge to the queue. If adding it would make the total weight negative, do not add it.