<p>This problem is a well studied problem: the problem of <strong>Journey planning in public transportation networks</strong>.<br>
Your approach based on Bellman-Ford might become problematic and too expensive depending on the network since you can't consider that a vertex has been 'visited', or that the shortest path to a vertex has been computed already during the algorithm's execution.<br>
These concepts (of 'visited', or of 'the shortest') can apply only to single objective shortest paths problem. That is because given <code>u, v</code> a couple of vertices, there is a potentially exponential number of interesting paths, because you can't consider only the faster or the cheaper option. You have to keep in memory any path such that there is no other path that is cheaper AND faster, and this number of paths can quickly grow out of control if you start working on realistic networks (which can be pretty big, ~100k stops, and millions of trips).  </p>

<p>I suggest you read about the <strong>multi-objective shortest path problem</strong>, with the additional fact that usually, the graph representing the network is a time-dependent graph.<br>
I think it can be worthy for you to read <a href="http://www.filipyoo.com/multi-objectives-shortest-paths-algorithms-for-multi-transfer-flight-routes/" rel="nofollow noreferrer">this page</a> on multi objective shortest path to have an idea about the main techniques used in the field (The notion of Pareto-set, or of Pareto-frontier, is quite important to grasp regarding this problem), and even more the section 2 and 4 of <a href="https://arxiv.org/pdf/1504.05140.pdf" rel="nofollow noreferrer">this paper</a>, which describes the actual state of the art regarding such techniques.  </p>

<p>Despite seeming complex, most of them can run incredibly fast (hundreds of thousand times faster than a Dijkstra, and still much faster than any A*-based approach), and for some of them are not too hard to implement (for instance, the <a href="https://i11www.iti.kit.edu/extra/publications/dpsw-isftr-13.pdf" rel="nofollow noreferrer">CSA</a> is not too complex, and runs pretty fast, it can compute a simple query in a few miliseconds on a country sized network). </p>
Modifying the Bellman-Ford Algorithm to maintain an ordered list based on cost
<p>So suppose you are searching for a train ride. You would be interested in the price of the ride and also the amount of time the ride will take. Now suppose that you have a graph where each edge has a cost and a duration and you want to find the shortest duration path in the graph that doesn't go over a given maximum cost (There might be multiple edges between any two vertices).</p>

<p>This is the problem I have. I think the best way to approach this problem is to modify the bellman-ford algorithm.</p>

<p>This is what I have so far:</p>

<pre><code>  // A struct to represent an Edge in graph
   struct Edge
   {
     int source, dest, cost, duration;
   };

   // A struct to reporesented a connected, directed 
   //and wieghted graph
   struct Graph
   {
     int V, E;
     struct Edge* edge;
   };

   // Creates Graph with V vertices and E edges
   struct Graph* createGraph(int V, int E)
   {
      struct Graph* graph = new (struct Graph);
      graph -&gt; V = V;
      graph -&gt; E = E;
      graph -&gt; edge = new Edge[E];
      return graph;
    } 
</code></pre>

<p>I have already filled the structs with all the information they need. Now I just need to "organize" the data based on cost. So i realize that for each vertex i need to store a list of paths that lead to it. For each edge i consider ill need to copy the paths from the first vertex list to the second vertex list (adding cost and distance). But how do I actually go about coding this, that the part I am stuck on. </p>