Ein wichtiges graphentheoretisches Problem ist die Bestimmung eines kürzesten, schnellsten oder sparsamsten Weges zwischen zwei Punkten. Dazu wird jeder Kante ein Wert zugeordnet, und man sucht einen Weg mit minimaler Summe dieser Werte. Der bekannteste Lösungsalgorithmus ist der Algorithmus von Dijkstra, der allerdings bei negativen Werten versagen kann. Der Floyd-Warshall-Algorithmus kann damit umgehen, ist aber deutlich aufwändiger. Das in gewisser Weise gegenteilige Probleme ist das Finden eines längsten Weges in einem azyklischen Graphen. Dieses Problem entsteht zum Beispiel in Ablaufplänen, wenn einzelne Schritte teilweise gleichzeitig zu und teilweise erst nach anderen Schritten ausgeführt werden können. Die Gesamtzeit des Projektes ergibt sich dann durch die maximale Zeit, die aufeinanderfolgende Schritte brauchen.