Costs
This option finds a minimum cost path from a source node to a destination through costed links.
The first line specifies the calculation required. It must contain
format costs
| Column | Description |
|---|---|
| 1 | g for graph |
| 2 | 0 ( default ) edges are undirected 1 edges are directed |
| 3 | 0 ( default ) for undirected edge cost different is each direction 1 cost applies in both directions |
If present, this must be the second line. If absent the default values are used.
| Column | Description |
|---|---|
| 1 | l for link |
| 2 | src node name |
| 3 | dst node name |
| 4 | cost |
Link costs can be negative. In this case an offset cost will be added to every link so that all costs are zero or positive, and subtracted from the total cost of the path displayed. Interpretation of the result when negative costs are present requires care.
| Column | Description |
|---|---|
| 1 | s |
| 2 | starting node name |
| Column | Description |
|---|---|
| 1 | e |
| 2 | node name -1 for paths to all nodes |
The appropriate algorithm is automatically applied depending on a check of the edge costs.
If all edge costs are the same, path is found using breadth first search.
If all edge costs are zero or positive, path is found using the Dijkstra algorithm. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
If some edge costs are negative, path is found using the Bellman-Ford algorithm. https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
Run time for running the Dijkstra algorithm to find the cheapest paths from one randomly selected vertex to every other vertex on large graphs downloaded from https://dyngraphlab.github.io/. Longest result from 3 runs using the graphex application.
| Vertex Count | Edge Count | Run time ( secs ) |
|---|---|---|
| 10,000 | 50,000 | 0.3 |
| 145,000 | 2,200,000 | 40 |