Алгоритм Форда-Беллмана (реализация на C++)

C++   7 Январь 2012  Автор статьи:  

Задан ориентированный взвешенный граф, содержащий, возможно, дуги отрицательного веса. Необходимо найти веса кратчайших путей от вершины v до всех остальных вершин.

Входные данные:

В первой строке записаны целые числа N и M – количество вершин и количество дуг соответственно (2\le N\le 1000, 0\le M\le 10000). Дальше идет M строк с тройками целых чисел X, Y, W, обозначающими, что дуга из X в Y имеет вес W (1\le X,Y\le N, |W|\le 1000). В последней строке записано число v – номер стартовой вершины (1\le v\le N).

Выходные данные:
Если в графе есть циклы отрицательного веса и потому не все кратчайшие пути определены, вывести «INCORRECT INPUT». В противном случае вывести N строк – веса кратчайших путей от вершины v до всех остальных вершин, включая её саму, в порядке возрастания номера второй вершины. Если до вершины дойти нельзя, то в соответствующей строке необходимо вывести «NO».

Реализация решения

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
const int inf=1E9;
int n,m,t[1000],i,j,v;
struct { int from,to,l; } edges[10000];
int main()
{
 scanf("%d%d",&n,&m);
 for (i=0;i<m;++i)
 {
  scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].l);
  --edges[i].from; --edges[i].to;
 }
 scanf("%d",&v); --v;
 for (i=0;i<n;++i) t[i]=inf;
 t[v]=0;
 for (i=1;i<=n;++i)
  for (j=0;j<m;++j)
   if (t[edges[j].from]<inf && t[edges[j].from]+edges[j].l<t[edges[j].to])
    if (i==n) { printf("INCORRECT INPUT"); return 0; } else
     t[edges[j].to]=t[edges[j].from]+edges[j].l;
 for (i=0;i<n;++i)
  if (t[i]==inf) printf("NO\n"); else printf("%d\n",t[i]);
}

Автор статьи – Сухов Сергей

  • Владимир

    Вот немножко оттюненный код:

    #include «stdafx.h»
    #include
    #include
    #include

    const int inf=1E9;
    int n,m,t[1000],i,j,v;
    struct { int from,to,l; } edges[10000];
    int main()
    {setlocale(LC_ALL, «Russian»);
    printf («Введите количество вершин графа:»);
    scanf(«%d»,&n);
    printf («Введите количество рёбер графа:»);
    scanf(«%d»,&m);
    for (i=0;in||edges[i].to>n)
    {printf («Не верно введён номер вершины»);
    getch();
    return 0;
    }
    }
    printf («Введите номер стартовой вершины:»);
    scanf(«%d»,&v); —v;
    for (i=0;i<n;++i) t[i]=inf;
    t[v]=0;
    for (i=1;i<=n;++i)
    for (j=0;j<m;++j)
    if (t[edges[j].from]<inf && t[edges[j].from]+edges[j].l<t[edges[j].to])
    if (i==n) { printf("Не все кратчайшие пути определены, т.к. в графе есть циклы отрицательного веса"); return 0; } else
    t[edges[j].to]=t[edges[j].from]+edges[j].l;
    for (i=0;i<n;++i)
    {printf ("Вес кратчайшего пути от заданной вершины до вершины %d : ", i+1);
    if (t[i]==inf) printf("до вершины дойти нельзяn"); else printf("%dn",t[i]);
    }
    getch();
    }

    • http://cybern.ru/ lordrp

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

Научиться программировать

  • на Delphi

  • на Java

  • на C++