[Close window]
dijkstra.awk - an AWK script to find shortest paths in a graph
|
|
dijkstra.awk is an AWK program to
solve shortest-path problems over directed graphs.
(g)awk is a script engine available by
default on most UNIX/Linux distributions.
If you're running Windows, you can get gawk.exe from
the UnxUtils package available at SourceForge.
The graph example.txt is provided to test the program
and to understand the basic idea. You can try it by running
gawk -f dijkstra.awk example.txt.
- usage: gawk -f dijkstra.awk <graphfile.txt>
- input: a text file with the graph edge list
and the requested solve commands
- output: the requested solution(s) will be
printed on standard output
Format of the input file
The input file will be read line by line.
Allowed commands are:
- <node1>,<node2>,<cost_float> to define a graph edge: node1 and node2 can be alphanumeric strings without spaces, cost_float must be a positive floating point number
- echo,<text> is used to print a message on standard output
- solve,<source>,<dest> calculates the shortest path from node source to node dest. Both source and dest can be alphanumeric strings without spaces
- format,<formatstring> defines the preferred output format for the solution. dijkstra.awk will substitute properly the symbols "[from]" (source node of an edge), "[to]" (destination node of an edge), "[cost]" (cost of an edge), "[pathcost]" (cost of the path from source up to the current point). When unspecified, default is "[from],\t[to],\t+[cost],\t[pathcost]"
- exit terminates program execution
Download
You can download the AWK script from here: [dijkstra.awk, 1.8 KB]
and the example.txt graph file from here: [example.txt, < 1 KB].