Is there a way to speed up this matrix (with only 1 & 0) multiplication & power operation?

General Usage Performance
,
21

In fact, the A* is not useful in this case, because we don’t have lower bounds on the shortest path.
Here is an example of to find the shortest path. I build directly the dual graph.

using Graphs
using Plots
using GraphRecipes
using SparseArrays

N = 10
g = Graphs.grid([N, N])
rows, cols = Int[], Int[]
for e in edges(g)
    if rand() < 0.7
        push!(rows, src(e))
        push!(cols, dst(e))
        push!(rows, dst(e))
        push!(cols, src(e))
    end
end
w = sparse(rows, cols, ones(Int, length(rows)), N^2, N^2)

result = a_star(g, 1, N*N, w)
println("cost is $(sum(w[src(e), dst(e)] for e in result))")

intact_edge = colorant"green"
broken_edge = colorant"red"
edgecolor = fill(intact_edge, N*N, N*N)
for e in edges(g)
    if w[src(e), dst(e)] == 0
        edgecolor[src(e), dst(e)] = broken_edge
    end
end
nodecolor = fill("", N*N)
nodecolor[src(result[1])] = "◼"
for e in result
    nodecolor[dst(e)] = "◼"
end
graphplot(g, curves=false, names=nodecolor, edgecolor=edgecolor)

The “:black_medium_square:” is a ugly hack because node colors are bugged in GraphRecipes.jl.

This does not necessarily gives the shortest path in terms of edges, but it will minimize the number of crossed edges. You can additionally minimize the length of the path by adding a small penalty on broken edges. (a weight smaller than 1/(4N) will be sufficient to always give the optimal path).

1 Like