Поиск наименьшего пути в графе

Алгоритм Дейкстры

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF=0x7fffffff;
int main()
{
  int s,f,a,b,n,i,j;
  cin>>n>>s>>f;
  f--;
  s--;
  int A[n][n],R[n],P[n];
  bool used[n];
  for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  {
    cin>>A[i][j];
    if(A[i][j]<0)A[i][j]=0;
  }
  for (i=0;i<n;i++)
  {
    R[i]=INF;
    P[i]=-1;
    used[i]=false;
  }
  R[s]=0;
  for(i=0;i<n;i++)
  {
//поиск минимального пройденного пути,
//который еще не проходили
    a=-1;
    b=INF;
    for(j=0;j<n;j++)
    {
      if (!used[j] && (a==-1 || R[j]<b))
      {
         b=R[j]; 
         a=j;
      }
    }
    if (a==-1) 
      break;
    else 
      used[a]=true;
//меняем значения путей, если надо
//и запоминаем путь
    for(j=0;j<n;j++)
    {
      if(A[a][j]!=0 && A[a][j]+R[a]<R[j])
      {
        R[j]=A[a][j]+R[a];
        P[j]=a;
       }
     }
   }
//восстанавливаем путь с конца
   int pos = f;
   vector <int> pr;
   while (pos != -1)
   {
      pr.push_back(pos);
      pos = P[pos];
   }
//переворачиваем путь
   reverse (pr.begin(),pr.end());
//выводим вершины пути, если путь найден
   if (R[f] == INF)
     cout << -1;
   else
   {
     cout<<R[f]<<endl;
     for (int i = 0;i < pr.size();i++)
        cout << pr[i]+1<< ' ';
   }
   return 0;
}

Алгоритм Флойда

#include <iostream>

using namespace std;

int main ()

{

    const int INF=0x7fffffff;

    int n, s, f;

    cin >> n >> s >> f;

    int d[n][n];

    f--;

    s--;

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

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

    {

        cin >> d[i][j];

    }

    for (int k=0; k<n; k++)

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

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

       if (d[i][k]>0 && d[k][j]>0 && 
          (d[i][j]==-1 || d[i][j]>d[i][k] + d[k][j]))

       {

        d[i][j] = d[i][k] + d[k][j];

       }

    cout<<d[s][f];

    return 0;

}

Представление графа в компьютере

Граф - это некая модель, схема, которая описывает некоторую задачу. Например, схема дорог между городами, связи между компьютерами и т. д. Важным элементом является информация о том, есть или нет связи между парой объектов (называемые вершинам графа), и если есть, то вводится дополнительная информация о связи (называемые ребрами графа): протяженность дороги, стоимость проезда, пропускная способность канала и т. д.

На рисунке представлен граф без стрелочек (называемый неориентированным графом). Если указать стрелочки, т. е. направление, то это будет ориентированный граф:

Чтобы описать граф обычно используют двумерный массив (матрица) или связный список.
1) Матрица инциденций:
строки-номера вершин; столбцы-номера ребер; если от вершины i идет ребро j, то на пересечении i-ой строки с j-ым столбцом стоит ее вес или 1, все остальные значения равны 0. 

Чтобы задать ориентированную дугу необходимо в строки, соответствующие начальной вершине, поставить её вес, а в соответствующие конечной вершине, её вес со знаком минус.

	1	2	3	4	5	6	7	8
1	1	1	0	0	0	0	0	0
2	-1	0	1	-1	0	0	0	0
3	0	0	0	1	0	-1	1	0
4	0	0	-1	0	1	0	0	1
5	0	1	0	0	1	1	0	0
6	0	0	0	0	0	0	1	-1

2) Матрица смежности:
строки и столбцы -номера вершин; если из вершины i в вершину j есть ребро, то на пересечении i-ой строки с j-ым столбцом стоит ее вес или 1, все остальные значения равны 0.

	1	2	3	4	5	6
1	0	1	0	0	1	0
2	0	0	0	1	0	0
3	0	0	0	0	0	1
4	0	0	1	0	0	1
5	1	0	1	0	0	0
6	0	0	0	0	0	0

Эти два способа занимают много места из-за их разреженности (много нулей).

3) Матрица списка ребер:
в 1-ой строке - номера вершин, из которых есть ребро; во 2-й строке - номера вершин, в которую это ребро направлено; в 3-ей строке - вес ребра.

	1	2	3	4	5	6	7
1	1	1	2	2	3	3	3
2	2	5	3	4	4	5	6

Если вес не указан, то 3-я строчка не используется.
4) Другой список:

	0	1	2	3	4	5	6
1	2	2	5	0	0	0	0
2	3	1	3	4	0	0	0
3	4	2	4	5	6	0	0
4	3	2	3	6	0	0	0
5	2	1	3	0	0	0	0
6	2	3	4	0	0	0	0

В каждой I-ой строке сначала записывается количество ребер, которые выходят из i-ой вершины, а затем перечисления номеров вершин, к которым эти ребра направлены. Можно и без нулевого столбца.
5) Связный список обычно используется для хранения большего количества информации об объекте или весе. Поле next направляет к следующей вершине, не обязательно соединенной с предыдущей. В поле info - информация о начале списка вершин, к которым есть ребра из данной вершины. Кроме этого в этом списке можно хранить информацию о весе ребер и другую информацию:
1->2->5
 |
V
2->1->3->4
 |
V
3->2->4->5->6
 |
V
4->2->3->6
 |
V
5->1->3
 |
V
6->3->4
Это похоже на предыдущий список без нулевого столбца и без лишних нулевых элементов. Такой способ наиболее экономичен.

Кроме обычных графов в задачах используют бинарные деревья (ориентированный граф):

Здесь вершина 1 называется корнем, от которого выходят две ветви: левая 2 и правая 3. Вершина 2 является листом дерева, т.к. из него нет ребер, а вершина 3 - подкорнем, у которого тоже есть листья 4 (левое) и 5 (правое).
Такое дерево тоже можно описать в виде матрицы списка ребер:

	1	2	3
1	1	2	3
2	2	0	0
3	3	4	5
4	4	0	0
5	5	0	0

где
1-й столбец - номера вершин, первый в списке - это корень дерева;
2-й столбец - номера левых вершин;
3-й столбец - номера правых вершин.
Если есть веса ребер, то можно добавить еще 2 столбца.

Или в виде связного списка, у которого вместо поля next есть два поля left и right - указатели на левую и правую вершину.
Немного о типе "связный список" для бинарного дерева:
type
    ptrspisok=^spisok;
    spisok=record
       info: integer;
       left: ptrspisok;
       right:ptrspisok;
     end;
var root:ptrspisok; - указатель на корень дерева;
      s:ptrspisok; - указатель на текущий элемент списка.

И для списка ребер (вершин):
type
    ptrspisok1=^spisok1;
    spisok1=record
       info: integer;
       ves: real;
       next:ptrspisok;
   end;

    ptrspisok=^spisok;
    spisok=record
       info: integer;
       curr:ptrspisok1;
       next:ptrspisok;
    end;
var root:ptrspisok; - указатель на начало списка;
      s:ptrspisok; - указатель на текущий элемент списка.

Как работать со списком - это тема другого сообщения.