I built the graph myself in something like:
Graph[edges, EdgeWeight -> weights]
which runs in < a second. The annotation route has never been my favorite as it is slow. Here is my code so you can see how I built up the graph:
str="###############\n#.......#....E#\n#.#.###.#.###.#\n#.....#.#...#.#\n#.###.#####.#.#\n#.#.#.......#.#\n#.#.#####.###.#\n#...........#.#\n###.#.#####.#.#\n#...#.....#.#.#\n#.#.#.###.#.#.#\n#.....#...#.#.#\n#.###.#.#.#.#.#\n#S..#.....#...#\n###############";
str=Characters/@StringSplit[str,"\n"];
posses=Position[str,"."|"E"|"S",{2}];
start={1,-1}FirstPosition[str,"S",Missing[],{2}];
stop={1,-1}FirstPosition[str,"E",Missing[],{2}];
posses[[All,2]]*=-1;
dirs={{0,1},{1,0},{0,-1},{-1,0}};
rotations=Catenate@Table[
ss={p,#}&/@dirs;
Join[Append[#,1000]&/@Partition[ss,2,1,1],Append[#,1000]&/@Partition[Reverse[ss],2,1,1]]
,
{p,posses}
];
hs=CreateDataStructure["HashSet",posses];
moves=Catenate@Table[
conns=Select[{{p,#},{p+#,#},1}&/@dirs,hs["MemberQ",#[[2,1]]]&]
,
{p,posses}
];
gr=Graph[Join[DirectedEdge@@@rotations[[All,;;2]],DirectedEdge@@@moves[[All,;;2]]],EdgeWeight->Join[rotations[[All,3]],moves[[All,3]]]];
Min[GraphDistance[gr,{start,{0,-1}},{stop,#}]&/@dirs]
Not the neatest code, but hopefully understandable. It basically makes vertices with {x,y,direction} and then does the pathfinding. 10 milliseconds on the example, and less than 1 second on my input.
I think your way of adding and deleting edges works fine, but not fast if you do it 5000 times sequentially.
