Поиск кратчайшего пути в графе

 

Лабораторная работа №6

Поиск кратчайшего пути в графе

Цель работы : изучить основные алгоритмы поиска кратчайшего пути в графе.

Задание : В заданном ориентированном графк найти кратчайший путь от вершины А до вершины F.

 

 

 

 

Краткие теоретические  сведения

Результатом алгоритма поиска кратчайшего  пути является последовательность ребер, соединяющая заданные две вершины  и имеющая наименьшую длину среди  всех таких последовательностей.  
     На первый взгляд кажется, что мы можем воспользоваться алгоритмом построения МОД, чтобы отбросить лишние ребра, а затем взять путь, соединяющий заданные вершины в построенном остовном дереве. К сожалению, такие действия не всегда приводят к нужному результату.  
     Напомним, что алгоритм построения МОД нацелен на поиск дерева с минимальным суммарным весом ребер. Рассмотрим, например, "циклический" граф, то есть такой граф, в котором первая вершина соединена со второй, вторая - с третьей, и так далее, а последняя вершина в свою очередь соединена с первой. Такой граф представляет собой просто кольцо, каждая вершина в котором соединена с двумя другими. Пример такого графа с шестью вершинами приведен на рис. 1 (а). 

 
     Обратите внимание на то, что вес каждого ребра равен 1 за исключением ребра, соединяющего вершины A и B, вес которого равен 2. Алгоритм построения минимального остовного дерева выберет все ребра веса 1, отбросив единственное ребро веса 2. Это означает, однако, что путь от A к B в минимальном остовном дереве должен проходить через все остальные вершины, а его длина равна 5 (рис. 1 (б)). Ясно, что он не является кратчайшим, поскольку в исходном графе вершины A и B соединены ребром длины 2.  
 
Алгоритм Дейкстры  
     Жадный алгоритм построения минимального остовного дерева непригоден для поиска кратчайшего пути между двумя вершинами, поскольку на каждом проходе он учитывает длину лишь одного ребра. Если же изменить его так, чтобы при выборе ребра, ведущего в кайму, он выбирал ребро, являющееся частью кратчайшего пути в целом пути из начальной вершины, то мы получим требуемый результат. Точнее говоря, вот измененный алгоритм:

 

выбрать начальную вершину

создать начальную кайму  из вершин, соединенных с начальной

while вершина назначения не достигнута do

выбрать вершину каймы  с кратчайшим расстоянием до начальной

добавить эту вершину  и ведущее в нее ребро к  дереву

изменить кайму путем  добавления к ней вершин,

соединенных с вновь  добавленной

for всякой вершины каймы do

приписать к ней ребро, соединяющее ее с деревом и

завершающее кратчайший путь к начальной вершине

end for

end while

 

 

Текст программы:

Файл graph.h

 

class Vertex {

public:

    Vertex();

    ~Vertex();

    void setName(char aName) {

        name=aName;

    };//функция задает имя вершине

    void output();//вывод на экран вершины

    char getName() {

        return name;

    };

    int getIndex() {

        return index;

    };

private:

    int index;//уникальный идентификатор  вершины

    char name;//имя вершины

    static int counter;//количество созданных вершин(счетчик вершин)

};

 

 

 

 

 

 

 

 

 

 

 

 

 

class Rib {

public:

    Rib();

    ~Rib();

    int getWeight()const {return weight;}//функция не меняет содержимого полей

    Vertex *getStart()const {return start;}

    Vertex *getEnd()const {return end;}

    void setWeight(int value) {weight=value;}

    void setStart(Vertex *aStart) {start=aStart;}

    void setEnd(Vertex *aEnd) {end=aEnd;}

    void output();//Вывод на экран ребра

private:

    int weight;//вес ребра

    Vertex *start;//начало ребра

    Vertex *end;//конец ребра

};

 

class Kaima;

 

class Graph {

public:

    Graph();

    ~Graph();

    void addRebro(Vertex *aStart, Vertex *aEnd, int aWeight);//добавление ребра

    void addVersh(char aName);//добавление  вершины

    void addVersh(Vertex *a);//добавление вершины по указателю

    Vertex *findVershByName(char aName);//поиск  вершины по имени

    virtual void output();//вывод графа

    int findMinWay(char fromName, char toName);//функция  нахождения минимального пути

 

 

 

 

public:

    int findOutRebra(Vertex *a);//находит ребра,выходящие из вершины

    int findInRebra(Vertex *a);//находит ребра, входящие в вершину

   

 

protected:

 

    int numReber;//количество ребер

    int numVersh;//количество вершин

    Rib **rebrs;//указатель на массив указателей на ребра

    Vertex **vershins;//указатель на массив указателей на вершины

 

protected:

    friend class Kaima;

    Rib **outRebra;//массив ребер,которые найдены в функции findOutRebra

    Rib **inRebra;//массив ребер,которые найдены в функции findInRebra

 

    int numOutReber;//количество найденых выходящих ребер

    int numInReber;//количество найденых исходящих ребер

    void addRebro(Rib *R);///<Добавляет ребро R по указателю

    bool isExist(Vertex *V);///<Проверяет присутствует-ли вершина V в графе. Возвращает: true|false - вершина найдена|не найдена среди вершин графа.

    bool isExist(Rib *R);///<Проверяет присутствует-ли ребро R в графе. Возвращает: true|false - ребро найдено|не найдено среди ребер графа.

};

 

 

 

 

 

 

class Kaima:public Graph {

public:

    Kaima();

    ~Kaima();

    void initKaima(Vertex* V, Graph* G);//Cоздает кайму(инициализация начала поиска). Добавление к дереву единственной вершины, присутствующей в графе G. Присоединение каймы.

    void output();

    int findWay(Vertex *From,Vertex *A);//Возвращает расстояние края каймы A до вершины From (корень каймы).

    int findVershWhisMinWayFrom();//Нахождение индекса вершины, ребра и длины маршрута, путь до которой из начальной точки дерева будет минимальным.

   

    void add(int index, Graph * G);///Присоединение ребра и вершины каймы к дереву.   

private:

    int *lenPathTree;//Массив длин путей от начальной вершины до каждой вершины дерева.

 

    Vertex **kajmaVertexes;//Массив вершин каймы.

    Rib **kajmaRibs;//Массив ребер каймы.

    int *kajmaLenPath;//Массив длин путей до вершин каймы.

    int num ;//Количество вершин, ребер и элементов длин путей в кайме.

};

 

 

 

 

 

 

 

 

 

Файл versh.cpp

#include "graph.h"

#include <iostream>

 

int Vertex::counter=0;

 

Vertex::Vertex() {

   index=++counter;

    name=0;

}

 

Vertex::~Vertex()

{

}

 

void Vertex::output()

{

    std::cout<<"Versh:"<<name<<"("<<index<<")";

    std::cout.flush();

}

 

Файл rebro.cpp

#include "graph.h"

#include <iostream>

 

Rib::Rib()

{

    weight=0;

    start=0;

    end=0;

}

 

Rib::~Rib()

{

 

}

 

void Rib::output()

{

    std::cout<<"Rib:";

    start->output();

    std::cout<<"->";

    end->output();

    std::cout<<"; Weight="<<weight;

    std::cout.flush();

}

 

 

Файл kaima.cpp

#include "graph.h"

#include <iostream>

 

Kaima::Kaima():Graph(), num(0)

{

    kajmaVertexes=new Vertex*[100];

    kajmaRibs=new Rib*[100];

    kajmaLenPath=new int[100];

 

    lenPathTree=new int[100];

}

 

Kaima::~Kaima()

{

    num=0;

    delete kajmaVertexes;

    delete kajmaRibs;

}

 

 

int Kaima::findVershWhisMinWayFrom()

{

    int res=0;//результирующая  вершина,до которой минимальный  путь

    int minWay=2000000000;

    for(int i=0; i<num; ++i)

    {

        Vertex *s=kajmaRibs[i]->getStart();

        int s_index=-1;//переменная, в которую будет  записываться инекс вершины,до которой минимальный путь

        for(int j=0; j<numVersh; ++j)

        {

            if(vershins[j]==s)

            {

                s_index=j;

                break;

            }

        }

        int len=lenPathTree[s_index]+kajmaRibs[i]->getWeight();//длина до края коймы от начала дерева

        minWay=(len<minWay)?(res=i,len):minWay;//если len<minWay, то res присваевается индекс того,что  мы ищем и возвращается len

    }

    return res;

}

 

 

int Kaima::findWay(Vertex* From, Vertex* A)

{

    int lenWay=0;

    Vertex *temp=A;//промежуточная  переменная

    std::cout<<"Результирующий  путь из конца в начало:"<<std::endl;

    while(temp!=From)

    {

temp->output();

std::cout<<"<-";

        findInRebra(temp);

        if(numInReber==1)

        {

            temp=inRebra[0]->getStart();

            lenWay+=inRebra[0]->getWeight();

        }

        else

            return 2000000000;

    }

    From->output();

    std::cout<<"="<<lenWay<<std::endl;

    return lenWay;

}

 

 

void Kaima::initKaima(Vertex *V, Graph* G)

{

    num=0;

    numVersh=0;

    numReber=0;

    lenPathTree[numVersh]=0;

    if(G && G->isExist(V))//Вершина  присутствует в графе.

    {

 

        addVersh(V);//добавляем вершину в дерево

 

        G->findOutRebra(V);//в графе ищем исходящие  ребра из этой вершины

        for(int i=0; i<G->numOutReber; ++i)

        {

            kajmaRibs[num]=G->outRebra[i];//добавляем исходящее  из вершины V графа G ребро в  кайму

            kajmaVertexes[num]=G->outRebra[i]->getEnd();//добавляем  вершину,которая присоеденена к исходящим ребру

            kajmaLenPath[num]=G->outRebra[i]->getWeight();//запоминается  в кайме вес ребра

            ++num;

        }

    }

    else

        std::cout<<"V not Exist in G"<<std::endl;

}

 

 

void Kaima::add (int index, Graph* G)

{

lenPathTree[numVersh]=kajmaLenPath[index];//добавляется расстояние от этой вершины до начала дерева

 

    addVersh(kajmaVertexes[index]);//добавляется  вершина из каймы в дерево

    addRebro(kajmaRibs[index]);//добавляется  ребро этой вершины из каймы  в дерево

    G->findOutRebra(kajmaVertexes[index]);//поиск по графу исходящих из присоед.вершины ребра

 

    for(int i=index; i+1<num; ++i)//исключение из каймы добавленной в дерево вершины,ребра

    {

        kajmaVertexes[i]=kajmaVertexes[i+1];

        kajmaRibs[i]=kajmaRibs[i+1];

        kajmaLenPath[i]=kajmaLenPath[i+1];

    }

    --num;//уменьшается  количество вершин в кайме

    for(int i=0; i<G->numOutReber; ++i)//к добавленной вершине присоеденяется  ее кайма

    {

        kajmaRibs[num]=G->outRebra[i];

        kajmaVertexes[num]=G->outRebra[i]->getEnd();

        kajmaLenPath[num]=G->outRebra[i]->getWeight();

        ++num;

    }

 

}

 

 

void Kaima::output()

{   std::cout<<"Kaima:";

   

std::cout<<"Graph:"<<std::endl;

    for(int i=0; i<numReber; ++i)

    {   rebrs[i]->output();

        std::cout<<"\n";

    }

 

    for(int i=0; i<numVersh; ++i)

    {   vershins[i]->output();

std::cout<<" "<<lenPathTree[i]<<std::endl;

    }

 

    for(int i=0; i<num; ++i)

    {

        kajmaRibs[i]->output();

        std::cout<<"\t";

        kajmaVertexes[i]->output();

        std::cout<<"\t";

        std::cout<<" "<<std::endl;

    }

}

 

Файл graph.cpp

#include "graph.h"

#include <iostream>

 

Graph::Graph()

{

    rebrs=new Rib*[100];

    vershins=new Vertex*[100];

    numReber=0;

    numVersh=0;

    outRebra=new Rib*[100];

    inRebra=new Rib*[100];

    numOutReber=0;

    numInReber=0;

}

 

Graph::~Graph()

{

    for(int i=0; i<numReber; ++i)

        delete rebrs[i];

 

    for(int i=0; i<numVersh; ++i)

        delete vershins[i];

 

    delete rebrs;

    delete vershins;

}

 

 

void Graph::addRebro(Vertex *aStart, Vertex *aEnd, int aWeight)

{

    if(aStart!=0&&aEnd!=0)

    {

        Rib *a=new Rib;//создается ребро

        rebrs[numReber++]=a;//в массив добавляется  ребро,кол-во ребер увеличивается на 1

        a->setStart(aStart);//связываем ребро с  вершинами

        a->setEnd(aEnd);

        a->setWeight(aWeight);

    }

}

 

void Graph::addVersh(char aName)

{

    Vertex *a=new Vertex;

    vershins[numVersh++]=a;

    a->setName(aName);

}

 

 

void Graph::output()

{

    std::cout<<"Graph:"<<std::endl;

    for(int i=0; i<numReber; ++i)

    {   rebrs[i]->output();

        std::cout<<"\n";

    }

 

    for(int i=0; i<numVersh; ++i)

    {   vershins[i]->output();

        std::cout<<"\n";

    }

 

    std::cout.flush();//команда очистки буфера

}

 

Vertex* Graph::findVershByName(char aName)

{

    for(int i=0; i<numVersh; ++i)

        if(vershins[i]->getName()==aName)

            return vershins[i];

    return 0;

}

 

int Graph::findOutRebra(Vertex *a)

{

    numOutReber=0;

    for(int i=0; i<numReber; ++i)

        if(rebrs[i]->getStart()==a)

            outRebra[numOutReber++]=rebrs[i];//если вершина  совпадает с начальной вершиной  какого-либо ребра из массива  ребер,то добавляем найденное  ребро в массив найденных ребер  и увеличиваем количество найд. ребер

    return numOutReber;

}

 

int Graph::findInRebra(Vertex *a)

{

    numInReber=0;

    for(int i=0; i<numReber; ++i)

        if(rebrs[i]->getEnd()==a)

            inRebra[numInReber++]=rebrs[i];//если вершина совпадает  с начальной вершиной какого-либо ребра из массива ребер,то добавляем найденное ребро в массив найденных ребер и увеличиваем количество найд. ребер

    return numInReber;

}

 

void Graph::addVersh(Vertex *V)

{

    if(isExist(V)) return;//если  вершина присутствует в массиве,то выходим

    vershins[numVersh++]=V;//иначе  добавляет вершину

}

 

void Graph::addRebro(Rib* R)

{

    if(isExist(R)) return;

    rebrs[numReber++]=R;

}

 

 

bool Graph::isExist(Vertex* V)

{

    for(int i=0; i<numVersh; ++i)

        if(vershins[i]==V)

            return true;

    return false;

}

 

 

bool Graph::isExist(Rib *R)

{

    for(int i=0; i<numReber; ++i)

        if(rebrs[i]==R)

            return true;

    return false;

}

 

int Graph::findMinWay(char fromName, char toName)

{

    Kaima *a=new Kaima;//создаем  койму

    Vertex *from=findVershByName(fromName);//нахождение  указателя вершины по имени

    Vertex *to=findVershByName(toName);

    if(from==0 || to==0)

        return 2000000000;//если нет какой-либо из вершин,то найти расстояние нельзя

 

    a->initKaima(from, this);

 

 

    while(!a->isExist(to))//пока  искомая точка не добалена  в дерево

    {

        int index=-1;

        index=a->findVershWhisMinWayFrom();//записывается  индекс вершины с минимальным путем

        a->add(index,this);//добавляется в граф

    }

    int minWay=a->findWay(from,to);//минимальный  искомый путь

    delete a;

return minWay;

}

 

Файл main.cpp

#include "graph.h"

#include <iostream>

 

int main()

{

    Graph A;

    A.addVersh('A');

    A.addVersh('B');

    A.addVersh('C');