algo for reducing a graph while preserving edge values along paths from a start node to an end node

Question

I have a directed cyclic graph with values at edges but no values at nodes.

The graph has a start node and an end node, and I want to preserve the set of paths through the graph but I don't care about the nodes on the path, only the edge values. Example below.

Are there any algorithms that will produce a smaller graph that preserves that property?

The graph might have 10's of thousands of nodes, but not millions. The number of edges per node is small w.r.t. the number of nodes.

Conservative heuristics are welcome.

As an example, where O is a node, and a number is the value of the adjacent edge:

  O --------> O -------> O 
    2         3
  ^                      |4
  |1                     v
      1    2    3    4
start -> O -> O -> O -> end

  |5                     ^
  v                      |8

  O --------> O -------> O
    6           7

has two paths with edge values [1,2,3,4] from start to end, so one is redundant, and I would be happy to reduce the above to

  O --------> O -------> O 
    2         3
  ^                      |4
  |1                     v

start                    end

  |5                     ^
  v                      |8

  O --------> O -------> O
    6           7

The graph can be cyclic, so in

          1
         /-\
         | /
         v/
start -> O -> O -> end
      1    1    2

a simpler graph would eliminate the second 1 transition to leave only the self-edge:

          1
         /-\
         | /
         v/
start -> O -> end
      1    2

Answer 1

Implication Charts did what I need. They're O(n**2) space-wise on the number of nodes, but that's manageable in my situation.

Answer 2

I would iterate through all nodes that are not the start and end and proceed to remove them. When removing a node you add another edge between all nodes that were connected through this node (watch direction since its a directed graph). The thing to remember is that if you try to add an edge that already exists due to this process - make sure to keep the edge with the smaller weight (that's the key).