Identifying shortest paths
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.
1. A non-transitory machine-readable storage medium storing instructions executable by a hardware processor of a computing device for identifying shortest paths, wherein the instructions, when executed, cause the hardware processor to:
access an edge table that specifies, for each edge of a graph that includes a plurality of nodes, an edge source node, an edge destination node, and an edge distance value indicating a distance between the edge source node and the edge destination node;
create a current path table from the nodes of the graph, wherein the current path table specifies a plurality of paths between the nodes of the graph and, for each path, a path source node, a path destination node, a path distance from the path source node to the path destination node, and a node path specifying each node included in the path between the path source node and the path destination node;
for each path in the current path table that has a path destination node that matches an edge source node of an edge included in the edge table, add a new path to the current path table, wherein the new path added to the current path table specifies: a sum of the edge distance value of the edge and the path distance of the path as a new path distance;
determine matching paths in the current path table that have a same path source node and a same path destination node;
identify a shortest path among the matching paths in the current path table, wherein the shortest path among the matching paths is a path that has a smallest path distance; and
remove, from the current path table, each matching path that is not the shortest path.
2. The non-transitory machine-readable storage medium of claim 1 , wherein the new path added to the current path table further specifies:
the path source node of the path as a new path source node;
the edge destination node as a new path destination node; and
the edge destination node appended to the node path as a new node path.
3. The non-transitory machine-readable storage medium of claim 1 , wherein the instructions further cause the hardware processor to:
determine, in response to determining that no paths included in the current path table are identified as an unknown path, that the current path table specifies each shortest known path between the nodes in the graph.
4. The non-transitory machine-readable storage medium of claim 1 , wherein the instructions further cause the hardware processor to:
determine that at least one path included in the current path table is identified as an unknown path, and in response to the determination:
identify each unknown path as a shortest known path; and
for each unknown path having a path destination node that matches an edge source node of an edge included in the edge table, add a second new path to the current path table, the second new path specifying:
the path source node as a second new path source node;
the edge destination node as a second new path destination node;
a sum of the edge value and the path distance as a second new path distance; and
the edge destination node appended to the node path as a second new node path.
5. The non-transitory machine-readable storage medium of claim 4 , wherein the instructions further cause the hardware processor to:
remove, from the current path table, matching second new paths that are not a shortest path, where the matching second new paths have a same path source node and a same path destination node.
6. The non-transitory machine-readable storage medium of claim 5 , wherein the instructions further cause the hardware processor to:
determine, in response to determining that no paths included in the current path table are identified as an unknown path, that the current path table specifies each shortest known path between the nodes in the graph.
7. The non-transitory machine-readable storage medium of claim 1 , wherein:
the current path table includes one starting path for each of the nodes in the graph, a path source node of the starting path matching a path destination node of the starting path.
8. A computing device for identifying shortest paths, the computing device comprising:
a hardware processor; and
a data storage device storing instructions that, when executed by the hardware processor, cause the hardware processor to:
access an edge table that specifies, for each edge of a graph that includes a plurality of nodes, an edge source node, an edge destination node, and an edge distance value indicating a distance between the edge source node and the edge destination node;
create an original path table that specifies, for each node of the graph, an original path that specifies the node as a path source node, the node as a path destination node, a path distance of zero from the path source node to the path destination node, and a node path specifying the node;
add each original path from the original path table to a current path table;
for each path in the current path table that has a path destination node that matches an edge source node of an edge included in the edge table, add a new path to the current path table, wherein the new path added to the current path table specifies: a sum of the edge distance value of the edge and the path distance of the path as a new path distance;
determine matching paths in the current path table that have a same path source node and a same path destination node;
identify a shortest path among the matching paths in the current path table, the shortest path being a path that has a smallest path distance; and
remove, from the current path table, each matching path that is not the shortest path.
9. The computing device of claim 8 , wherein:
each original path is flagged as an inactive path;
each new path is flagged as an active path; and
wherein the instructions further cause the hardware processor to:
create a second current path table that includes each original path of the original path table and each new path, wherein each original path and each new path is flagged as an inactive path in the second current path table; and
for each path that i) is flagged as an active path in the second current path table, and ii) has a path destination node that matches an edge source node of an edge included in the edge table, add a second new path to the second current path table, the second new path specifying:
the path source node of the path as a second new path source node;
the edge destination node of the path as a second new path destination node;
a sum of the edge value and the path distance as a second new path distance; and
the edge destination node appended to the node path as a second new node path.
10. The computing device of claim 9 , wherein the instructions further cause the hardware processor to:
identify, from the second current path table, paths that match one another based on matching path source nodes and matching path destination nodes;
for paths that match one another, identify a shortest path, the shortest path being identified based on path distances specified by each matching path; and
discard each matching path that is not the shortest path.
11. The computing device of claim 10 , wherein:
each new path in the second current path table is flagged as an inactive path;
each second new path in the second current path table is flagged as an active path; and
wherein the instructions further cause the hardware processor to:
determine, in response to determining that no paths included in the second current path table are identified as an unknown path, that the second current path table specifies each shortest known path between the nodes in the graph.
12. The computing device of claim 8 , wherein the new path added to the current path table, further specifies:
the path source node of the path as a new path source node;
the edge destination node of the path as a new path destination node; and
the edge destination node appended to the node path as a new node path.
13. A method for identifying shortest paths, implemented by a hardware processor, the method comprising:
accessing an edge table that specifies, for each edge of a graph that includes a plurality of nodes, an edge source node, an edge destination node, and an edge distance value indicating a distance between the edge source node and the edge destination node;
creating a first path table by selecting each path from a path table that specifies a plurality of paths between the plurality of nodes of the graph and, for each path, a path source node, a path destination node, a path distance from the path source node to the path destination node, a node path specifying each node included in the path between the path source node and the path destination node, and a path flag indicating whether the path is active;
for each path included in the first path table, setting the path flag to indicate that the path is inactive;
creating a second path table by:
identifying each path that i) is included in the first path table, ii) has a path flag indicating the path is active, and iii) has a path destination node that matches an edge source node of an edge included in the edge table; and
for each identified path, adding, to the second path table, a new path specifying:
the path source node of the as a new path source node;
the edge destination node of the edge as a new path destination node;
a sum of the edge value of the edge and the path distance of the identified path as a new path distance; and
the edge destination node appended to the node path of the identified path as a new node path;
combining the first path table and the second path table to create a combined path table;
determining matching paths in the combined path table that have a same path source node and a same path destination node; and
identifying a shortest path among the matching paths in the combined path table, the shortest path being a path that has a smallest path distance from the path source node to the path destination node.
14. The method of claim 13 , wherein the first path table specifies one starting path for each of the plurality of nodes of the graph, a path source node of the starting path matching a path destination node of the starting path.
15. The method of claim 13 , further comprising:
discarding, from the combined path table, each matching path that is not identified as the shortest path.
16. The method of claim 14 , further comprising:
determining that each path flag of each path included in the combined path table indicates that the path is inactive; and
in response to the determination, determining that the combined path table is a shortest path table specifying the shortest paths between the plurality of nodes of the graph.