Examples relate to identifying shortest paths. In one example, a computing device may: access an edge table that specifies, for each edge of a graph, an edge source, an edge destination, and an edge distance value; access a current path table that specifies paths between nodes of the graph and, for each path, a source node, a destination node, a distance, and a node path; identify each path included in the current path table as a shortest known path; and for each path having a destination node that matches an edge source node, add a new path to the current path table, the new path specifying: the source node as a new source; the edge destination as a new destination; a sum of the edge value and the path distance as a new distance; and the edge destination appended to the node path as a new node path.