Алгоритм поиска кратчайшего пути

[Anaya]

Дано:
матрица смежности ( две вершины соединены ребром - 1, не соединены - 0 )

Нужно:
Найти кратчайший путь из вершины k в вершину t. ( ну не суть как их обозвать - из произвольной в произвольную ).

Почему-то Дейсктру клинит ( подозреваю, что потому что "веса" всех ребер =1 )

Какой алгоритм будет наиболее эффективен??
( и вообще - какие алгоритмы тут можно применить? )
если еще и ссылочки на реализации на С/С++ - то вообще просто шикарно!!!

P.S.
Это нужно для диплома, чтобы создать видимо "долгого и мучительного выбора, с исследованиями эффективносит и т.д. и т.п." - помогите - до защиты 1.5 месяца ( как всегда, студентчество "тянет до последнего", простите)

Спасибо большое заранее всем откликнувшимся...

[Sands]

Можно посмотреть на algolist.manual.ru как по мне то один из немногих, где обьясняют нормально и примеры реализаций можно найти.

[bebabo]

вот реализация поиска пути в глубину от H.Вирта.  можно посмотреть в консольном режиме.

cуть происходящего):
есть лабиринт, в котором "1" обозначает проход, а "0" - стену.

1110110001111
1011101111101
1000101010101
1000111010111
1111100001000
0000100000000
0000111111111

Для того, чтобы найти путь из точки А (0,0) в точку Б (6, 12), пользуясь данным методом поиска, мы должны выбрать некую следующую позицию. В нашем варианте мы будем выбирать любую соседнюю ячейку (исключая ячейки по диагонали) в порядке по часовой стрелке: 1 - строкой выше, 2 - колонкой правее, 3 - строкой ниже, 4 - колонкой левее. Если новая позиция находится на пути к конечной точке - переходим на нее, если нет - выбираем другую позицию. При этом путь ведущий к цели будет помечаться "9", а путь ведущий в тупик - "2".
Вот как будет выглядеть поиск пути в глубину из точки А в точку Б:

9990220002222
1099902222202
1000902020202
1000922020222
1111900001000
0000900000000
0000999999999

Оказавшись в тупике, мы возвращаемся до тех пор, пока не оказываемся в позиции, из которой возможно сделать другой ход и вновь пытаемся достичь конечную точку.
 

Код:

//Position.h
//объявление класса Position

#ifndef POSITION
#define POSITION

class Position
{
private:
    int row;
    int column;
public:
    Position();
    Position(int row, int column);
    void setPosition(int row, int column);
    int getRow();
    int getColumn();
};
#endif

//Position.cpp
//методы класса Position

#include "Position.h"

Position::Position()
{
    row=0;
    column=0;
}

Position::Position(int row, int column)
{
    this->row=row;
    this->column=column;
}

void Position::setPosition(int row, int column)
{
    this->row=row;
    this->column=column;
}

int Position::getRow()
{
    return this->row;
}

int Position::getColumn()
{
    return this->column;
}

//Application.h
//

#ifndef APPLICATION
#define APPLICATION

#include <iostream>
#include "Position.h"

using namespace std;

class Application
{
    friend ostream& operator << (ostream& stream,
        Application& app);
public:
    Position generateInitialState();//генерирует начальное состояние - ввод начальных и конечных точек
    bool valid (Position& pos);//проверка корректности ввода
    void record (Position& pos);//отмечает пройденный путь как "9"
    bool done (Position& pos);//проверка текущей и конечной точек на совпадение
    void undo (Position& pos););//отмечает пройденный путь как "2"

    class Iterator
    {
    public:
        Iterator();
        Iterator (Position& pos);
        Position operator++ (int);
        bool atEnd();
    protected:
        void* fieldPtr;
    };
};
#endif

//BackTrack.h
//

#ifndef BACKTRACK
#define BACKTRACK

#include "Application.h";
#include "Position.h"

class BackTrack
{
public:
    BackTrack (const Application& app);
    bool tryToSolve (Position pos);//рекурсивная функция - попытка найти путь через выбранную позицию
protected:
    Application app;
};
#endif

//BackTrack.cpp
//

#include "BackTrack.h"

using namespace std;

BackTrack::BackTrack (const Application& app)
{
    this->app=app;
}

bool BackTrack::tryToSolve (Position pos)
{
    bool success = false;

    Application::Iterator itr(pos);
    while(!success && !itr.atEnd())
    {
        pos=itr++;
        if(!app.valid(pos))
        {
            app.record(pos);
            if(app.done(pos))
                success=true;
            else
            {
                success = this->tryToSolve(pos);
                if(!success)
                    app.undo(pos);
            }
        }
    }
    return success;
}

//Maze.cpp
//реализация методов класса Аpplication и установка значений лабиринта

#include <iostream>
#include <string>
#include "Application.h"

const short WALL=0;
const short CORRIDOR=1;
const short PATCH=9;
const short TRIED=2;
const short ROWS=7;
const short COLUMNS=13;

short grid [ROWS][COLUMNS] =
{
    {1,1,1,0,1,1,0,0,0,1,1,1,1},
    {1,0,1,1,1,0,1,1,1,1,1,0,1},
    {1,0,0,0,1,0,1,0,1,0,1,0,1},
    {1,0,0,0,1,1,1,0,1,0,1,1,1},
    {1,1,1,1,1,0,0,0,0,1,0,0,0},
    {0,0,0,0,1,0,0,0,0,0,0,0,0},
    {0,0,0,0,1,1,1,1,1,1,1,1,1},
};

Position start, finish;

using namespace std;

Position Application::generateInitialState()
{
    const string START_PROMT = "Введите начальные строку и колонку:";

    const string FINISH_PROMT = "Введите конечные строку и колонку:";

    int row, column;

    cout << START_PROMT;
    cin>>row>>column;
    start.setPosition(row,column);
    cout << FINISH_PROMT;
    cin>>row>>column;
    cin.get();
    finish.setPosition(row,column);       
    return start;
}

bool Application::valid(Position& pos)
{
    if(pos.getRow()>=0 && pos.getRow()<ROWS &&
        pos.getColumn()>=0 && pos.getColumn() < COLUMNS &&
        grid [pos.getRow()][pos.getColumn()] == CORRIDOR)
        return false;
    else
        return true;

}

void Application::record(Position& pos)
{
    grid[pos.getRow()][pos.getColumn()]=PATCH;
}

bool Application::done(Position& pos)
{
    if(pos.getRow()==finish.getRow()&&
        pos.getColumn()==finish.getColumn())
        return true;
    else
        return false;
}

void Application::undo(Position& pos)
{
    grid [pos.getRow()][pos.getColumn()]=TRIED;
}

ostream& operator<< (ostream& stream, Application& app)
{
    cout<<endl;//
    for(int row=0; row<ROWS; row++)//
    {
        for(int column=0; column<COLUMNS; column++)//
            cout<<grid[row][column]<<' ';//
        cout<<endl;//
    }
    return stream;
}

struct itrFields
{
    int row,
        column,
        direction;
};

Application::Iterator::Iterator(Position& pos)
{
    itrFields* itrPtr = new itrFields;//
    itrPtr->row=pos.getRow();//
    itrPtr->column=pos.getColumn();//
    itrPtr->direction=0;//
    fieldPtr=itrPtr;
}

Position Application::Iterator::operator ++ (int)
{
    itrFields* itrPtr = (itrFields*) fieldPtr;
    int nextRow=itrPtr->row,//
        nextColumn=itrPtr->column;

    switch(itrPtr->direction++)//
    {
    case 0: nextRow=itrPtr->row-1;//
        break;
    case 1: nextColumn=itrPtr->column+1;//
        break;
    case 2: nextRow=itrPtr->row+1;//
        break;
    case 3: nextColumn=itrPtr->column-1;//
        break;
    }

    Position next(nextRow, nextColumn);
    return next;
}

bool Application::Iterator::atEnd()
{
    return ((itrFields*)fieldPtr)->direction>=4;//
}

//BackTrackMain.cpp
//функция main

#include <iostream>
#include <string>
#include "BackTrack.h"
#include "Application.h"
#include "Position.h"

using namespace std;

int main()
{
    const string INITIAL_STATE = "Начальное состояние: \n";
    const string SUCCESS = "\n\n Решение найдено:";
    const string FAILURE =     "\n\n Решения нет";
    const string CLOSE_WINDOW_PROMT = "Нажмите Enter, чтобы закрыть окно";

    Application app;
    BackTrack b(app);

    cout<<INITIAL_STATE;//
    Position start = app.generateInitialState();
   
    cout<<app;//ввод начальных значений//

    if(app.valid(start))//проверка на корректность ввода
        cout<<FAILURE<<endl;//
    else
    {
        app.record(start);//помечаем пройденные ячейки как "9"
        if(app.done(start) || b.tryToSolve(start))
            cout<<SUCCESS<<endl<<app;//
        else
        {
            app.undo(start);
            cout<<FAILURE<<endl;//
        }
    }

    cout<<endl<<endl<<CLOSE_WINDOW_PROMT;//
    cin.get();

    return 0;
}

[Алексей++]

волновой алгоритм вам нужен ) Дёшево и сердито.
например
http://algolist.manual.ru/games/wavealg.php

[sfok]

под эти условия подойдет - алгоритм поиска пути A*, посмотрите вот здесь: h**p://scr1pter.blogspot.com/p/blog-page.html

[Dimka]

Почему-то Дейсктру клинит ( подозреваю, что потому что "веса" всех ребер =1 )

Пока я не вижу никаких проблем с Дейкстрой.

Где твоё понимание алгоритма, твоя реализация, твой пример и твой неправильный результат в этом примере?

bebabo, твоя матрица - это не матрица смежности, это просто рисунок лабиринта.

[Sla]

Dimka,
вот же некроманы

[Dimka]

Sla, а я на дату не посмотрел