Problems involving the determination of routes on networks arise in many different contexts. For example network flow problems in operations research, such as transportation and assignment problems, involve the determination of a succession of shortest or least-cost paths between commodity sources and sinks. Again, critical path analysis and certain scheduling problems involve the determination of longest paths on activity networks. Pathfinding problems of different kinds also arise in the design of logic networks, and in routing messages through congested communication networks. This paper presents an algebraic structure for the formulation and solution of such problems. After defining the algebraic structure and giving concrete examples applicable to different kinds of routing problems, we use it in a general analysis of a class of directed networks, in which each are has an associated measure (representing for instance a transportation cost, an activity duration, the state (open or closed) of a switch, or the probability of a communication link being available). It is then shown that all the routing problems mentioned above can be expressed in the same algebraic form, and that they can all be solved by variants of classical methods of linear algebra, differing from these only in the significance of the additive and multiplicative operations.