Editing Shortest path problem (section)

==General algebraic framework on semirings: the algebraic path problem==
{{expand section|date=August 2014}}
Many problems can be framed as a form of the shortest path for some suitably substituted notions of addition along a path and taking the minimum.  The general approach to these is to consider the two operations to be those of a [[semiring]]. Semiring multiplication is done along the path, and the addition is between paths. This general framework is known as the [[algebraic path problem]].<ref name="Pair1966">{{cite conference |first = Claude | last = Pair
| title= Sur des algorithmes pour des problèmes de cheminement dans les graphes finis |trans-title=On algorithms for path problems in finite graphs
| book-title = Théorie des graphes (journées internationales d'études) [Theory of Graphs (international symposium)]
| publisher = Dunod (Paris); Gordon and Breach (New York)
| date = 1967
| conference = Rome (Italy), July 1966
| page  = 271
| editor-last = Rosentiehl | editor-first = Pierre | editor-link = Pierre Rosenstiehl
| oclc = 901424694
}}</ref><ref>{{cite book
| first1 = Jean Claude | last1 = Derniame
| first2 = Claude | last2 = Pair
| title = Problèmes de cheminement dans les graphes |trans-title=Path Problems in Graphs
| publisher = Dunod (Paris)
| year = 1971
}}</ref><ref name="BarasTheodorakopoulos2010">{{cite book |first1=John |last1=Baras |first2=George |last2=Theodorakopoulos |title=Path Problems in Networks |url=https://books.google.com/books?id=fZJeAQAAQBAJ&pg=PA9|date=4 April 2010 |publisher=Morgan & Claypool Publishers |isbn=978-1-59829-924-3 |pages=9–}}</ref>

Most of the classic shortest-path algorithms (and new ones) can be formulated as solving linear systems over such algebraic structures.<ref name="GondranMinoux2008">{{cite book |first1=Michel |last1=Gondran |first2=Michel |last2=Minoux |title=Graphs, Dioids and Semirings: New Models and Algorithms |year=2008 |publisher=Springer Science & Business Media|isbn=978-0-387-75450-5|chapter=chapter 4}}</ref>

More recently, an even more general framework for solving these (and much less obviously related problems) has been developed under the banner of [[valuation algebra]]s<!-- not just [[valuation (algebra)]]! -->.<ref name="PoulyKohlas2012">{{cite book |first1=Marc |last1=Pouly |first2=Jürg |last2=Kohlas |title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons |isbn=978-1-118-01086-0 |chapter=Chapter 6. Valuation Algebras for Path Problems}}</ref>