Dijkstra's algorithm: Difference between revisions
Added AWK version
(added Free Pascal example) |
Salvipeter (talk | contribs) (Added AWK version) |
||
Line 1,667:
F > E 9
Total distance = 20</pre>
=={{header|AWK}}==
A very basic implementation in AWK. Minimum element in the queue is found by a linear search.
<syntaxhighlight lang="awk">
NF == 3 { graph[$1,$2] = $3 }
NF == 2 {
weight = shortest($1, $2)
n = length(path)
p = $1
for (i = 2; i < n; i++)
p = p "-" path[i]
print p "-" $2 " (" weight ")"
}
# Edge weights are in graph[node1,node2]
# Returns the weight of the shortest path
# Shortest path is in path[1] ... path[n]
function shortest(from, to, queue, q, dist, v, i, min, edge, e, prev, n) {
delete path
dist[from] = 0
queue[q=1] = from
while (q > 0) {
min = 1
for (i = 2; i <= q; i++)
if (dist[queue[i]] < dist[queue[min]])
min = i
v = queue[min]
queue[min] = queue[q--]
if (v == to)
break
for (edge in graph) {
split(edge, e, SUBSEP)
if (e[1] != v)
continue
if (!(e[2] in dist) || dist[e[1]] + graph[edge] < dist[e[2]]) {
dist[e[2]] = dist[e[1]] + graph[edge]
prev[e[2]] = e[1]
queue[++q] = e[2]
}
}
}
if (v != to)
return "n/a"
# Build the path
n = 1
for (v = to; v != from; v = prev[v])
n++
for (v = to; n > 0; v = prev[v])
path[n--] = v
return dist[to]
}
</syntaxhighlight>
Example:
<syntaxhighlight lang="bash">
$ cat dijkstra.txt
a b 7
a c 9
a f 14
b c 10
b d 15
c d 11
c f 2
d e 6
e f 9
a e
a f
f a
$ awk -f dijkstra.awk dijkstra.txt
a-c-d-e (26)
a-c-f (11)
f-a (n/a)
</syntaxhighlight>
=={{header|C}}==
| |||