Methods, systems, and computer-readable storage media for receiving data representative of the temporal graph, the data representing vertices, edges between vertices, and temporal features, determining a set of earliest-arrival dependencies, each earliest arrival dependency including an earliest feasible edge between vertices from a list of edges of the temporal graph, providing data representative of an edge-scan-dependency graph (ESD-graph) based on the data representative of the temporal graph, and the set of earliest-arrival dependencies, the ESD-graph including vertices representing edges of the temporal graph, and edges representing earliest-arrival dependencies between vertices, providing data representative of a level-assigned ESD-graph including a level assigned to each vertex of the ESD-graph, and determining earliest-arrival times between a source vertex, and each vertex of the temporal graph by executing a parallel edge scan of the level-assigned ESD-graph.