shortest-path-dijkstra.js

let str =
    "**************************\n" +
    "*S* *                    *\n" +
    "* * *  *  *************  *\n" +
    "* *   *    ************  *\n" +
    "*    *                   *\n" +
    "************** ***********\n" +
    "*                        *\n" +
    "** ***********************\n" +
    "*      *              G  *\n" +
    "*  *      *********** *  *\n" +
    "*    *        ******* *  *\n" +
    "*       *                *\n" +
    "**************************";

let strmap = str.split("\n").reduce(function (a, l) { a.push(l.split("")); return a; }, []);

const INF = null;

let field  = strmap.map(
    function (r, y) r.map(
        function (c, x) {
            return {
                x     : x,
                y     : y,
                str   : c,
                from  : null,
                done  : false,
                score : {
                    " " : INF,
                    "S" : 0,
                    "G" : INF
                }[c]
            };
        }));

field.at    = function (p, x, y) this[y] ? this[y][x] : undefined;
field.up    = function (p) field.at(p, p.x, p.y - 1);
field.down  = function (p) field.at(p, p.x, p.y + 1);
field.left  = function (p) field.at(p, p.x - 1, p.y);
field.right = function (p) field.at(p, p.x + 1, p.y);

field.__iterator__ = function (keyOnly) {
    for (let i = 0; i < this.length; ++i)
        for (let j = 0; j < this[i].length; ++j)
            yield keyOnly ? this[i][j] : [, this[i][j]];

    throw StopIteration;
};

field.remains = function () {
    while (true)
    {
        let minNode;

        for (let [, node] in Iterator(this))
        {
            if (node.str === "*" || node.done)
                continue;

            if (!minNode || smaller(node.score, minNode.score))
                minNode = node;
        }

        if (!minNode || minNode.score === INF)
            throw StopIteration;

        yield minNode;
    }
};

field.find  = function (c) {
    for (let [, node] in Iterator(this))
        if (node.str === c)
            return node;
    return null;
};

function smaller(s1, s2) (s1 === INF) ? false : (s2 === INF) ? true : (s1 < s2);

// ====================================================================== //

function dijkstra(f) {
    const directions = ["up", "right", "down", "left"];

    let remains = f.remains();

    for (let looking in remains)
    {
        let cand = looking.score + 1;

        for (let [, direction] in Iterator(directions))
        {
            let next = f[direction](looking);

            if (!next || next.str === "*")
                continue;

            if (smaller(cand, next.score))
            {
                next.score = cand;
                next.from  = looking;
            }
        }

        looking.done = true;
    }
}

dijkstra(field);

// ====================================================================== //

let start = field.find("S");
let goal  = field.find("G");

for (let node = goal.from; node !== start; node = node.from)
    strmap[node.y][node.x] = "$";
    
window.alert(strmap.map(function (r) r.join("")).join("\n"));

shortest-path.js

// http://okajima.air-nifty.com/b/2010/01/post-abc6.html

let str =
    "**************************\n" +
    "*S* *                    *\n" +
    "* * *  *  *************  *\n" +
    "* *   *    ************  *\n" +
    "*    *                   *\n" +
    "************** ***********\n" +
    "*                        *\n" +
    "** ***********************\n" +
    "*      *              G  *\n" +
    "*  *      *********** *  *\n" +
    "*    *        ******* *  *\n" +
    "*       *                *\n" +
    "**************************";

let strmap = str.split("\n").reduce(function (a, l) { a.push(l.split("")); return a; }, []);

let field  = strmap.map(
    function (r, y) r.map(
        function (c, x) {
            return {
                x     : x,
                y     : y,
                str   : c,
                from  : null,
                score : {
                    " " : -1,
                    "S" : 0,
                    "G" : -1
                }[c]
            };
        }));

field.at    = function (p) this[p.y][p.x];
field.up    = function (p) this[p.y - 1][p.x];
field.down  = function (p) this[p.y + 1][p.x];
field.left  = function (p) this[p.y][p.x - 1];
field.right = function (p) this[p.y][p.x + 1];

field.find  = function (c) {
    for (let i = 0; i < this.length; ++i)
    {
        for (let j = 0; j < this[i].length; ++j)
        {
            if (this[i][j].str === c)
                return this[i][j];
        }
    }

    return null;
};

function equal (p1, p2) p1 && p2 && p1.x === p2.x && p1.y === p2.y;

// ====================================================================== //

let start = field.find("S");
let goal  = field.find("G");

function step(current) {
    if (equal(current, goal))
    {
        current.score = -1;
        current.from  = null;

        return [goal];
    }

    let stack;

    for (let [, direction] in Iterator(["up", "right", "down", "left"]))
    {
        let next = field[direction](current);

        if (next.str === "*" || equal(next.from, current))
            continue;

        if (next.score < 0 || current.score + 1 < next.score)
        {
            next.score = current.score + 1;
            next.from  = current;

            let tmp = step(next);

            if (tmp)
            {
                if (!stack || tmp.length < stack.length)
                {
                    stack = tmp;
                }
            }
        }
    }

    current.score--;
    current.from = null;

    if (stack)
    {
        stack.push(current);
        return stack;
    }

    return null;
}

let result = step(start);
result.pop();                   // remove goal
result.shift();               // remove start

result.forEach(function (o, i) strmap[o.y][o.x] = "$");

window.alert(strmap.map(function (r) r.join("")).join("\n"));