b'\n_START_ARTICLE_\nBelmana\xe2\x80\x94Forda algoritms\n_START_PARAGRAPH_\nBelmana\xe2\x80\x94Forda algoritms ir algoritms \xc4\xabs\xc4\x81k\xc4\x81 ce\xc4\xbca mekl\xc4\x93\xc5\xa1anai starp doto un p\xc4\x81r\xc4\x93j\xc4\x81m virsotn\xc4\x93m sv\xc4\x93rtos grafos. At\xc5\xa1\xc4\xb7ir\xc4\xabb\xc4\x81 no Deikstras algoritma Belmana\xe2\x80\x94Forda algoritms pie\xc4\xbcauj negat\xc4\xabvus \xc5\xa1\xc4\xb7aut\xc5\x86u svarus, bet ir l\xc4\x93n\xc4\x81ks, t\xc4\x81p\xc4\x93c parasti tiek izmantots, ja graf\xc4\x81 ir \xc5\xa1\xc4\xb7autnes ar negat\xc4\xabviem svariem.\n_START_SECTION_\nAlgoritma apraksts\n_START_PARAGRAPH_\nDots sv\xc4\x93rts grafs  ar \xc5\xa1\xc4\xb7aut\xc5\x86u svaru funkciju  un s\xc4\x81kuma virsotni ._NEWLINE_Izveidojams matricas , kas satur\xc4\x93s \xc4\xabs\xc4\x81ko ce\xc4\xbcu no  uz virsotni  caur  \xc5\xa1\xc4\xb7autn\xc4\x93m un , kas satur iepriek\xc5\xa1\xc4\x93jo virsotni \xc5\xa1\xc4\x81d\xc4\x81 ce\xc4\xbc\xc4\x81._NEWLINE_Matric\xc4\x81  vien\xc4\xabgais ce\xc4\xbc\xc5\xa1 no , kas satur 0 \xc5\xa1\xc4\xb7autnes ir tikai l\xc4\xabdz pa\xc5\xa1ai  un t\xc4\x81 garums ir 0. T\xc4\x81d\xc4\x93j\xc4\x81di . Visu p\xc4\x81r\xc4\x93jo ce\xc4\xbcu s\xc4\x81kotn\xc4\x93j\xc4\x81s v\xc4\x93rt\xc4\xabbas ir ._NEWLINE_Algoritms ir sekojo\xc5\xa1s:_NEWLINE_for _NEWLINE_  for  to _NEWLINE_    do for  to _NEWLINE_  do for _NEWLINE_    if _NEWLINE_      then _NEWLINE_           _NEWLINE_Algoritma rezult\xc4\x81t\xc4\x81 matrica  satur \xc4\xabs\xc4\x81kos ce\xc4\xbcus no  uz virsotni  caur da\xc5\xbe\xc4\x81diem \xc5\xa1\xc4\xb7aut\xc5\x86u skaitiem . Pats \xc4\xabs\xc4\x81kais ce\xc4\xbc\xc5\xa1 starp  un  ir \xc4\xabs\xc4\x81kais no tiem._NEWLINE_Kad noskaidrots pats \xc4\xabs\xc4\x81kais ce\xc4\xbc\xc5\xa1 caur  \xc5\xa1\xc4\xb7autn\xc4\x93m, pilnu ce\xc4\xbcu mas\xc4\xabv\xc4\x81  var ieg\xc5\xabt \xc5\xa1\xc4\x81di:_NEWLINE_while _NEWLINE_ _NEWLINE_ _NEWLINE_ return p_NEWLINE_Ja nepiecie\xc5\xa1ams noskaidrot tikai \xc4\xabs\xc4\x81k\xc4\x81 ce\xc4\xbca garumu un nav nepiecie\xc5\xa1ams zin\xc4\x81t visu ce\xc4\xbcu izmantojams \xc5\xa1\xc4\x81ds algoritms:_NEWLINE_for _NEWLINE_ do for  to _NEWLINE_ do for _NEWLINE_  return _NEWLINE_\xc5\xa0\xc4\xab algoritma rezult\xc4\x81t\xc4\x81 mas\xc4\xabva  elements  satur\xc4\x93s \xc4\xabs\xc4\x81k\xc4\x81 ce\xc4\xbca garumu starp virsotn\xc4\x93m  un .\n_START_SECTION_\nKoda piem\xc4\x93ri\n_START_PARAGRAPH_\nBelmana\xe2\x80\x94Forda algoritma realiz\xc4\x81cija C_NEWLINE_/* Bellman-Ford Implementation */_NEWLINE_ #include <limits.h>_NEWLINE_ #include <stdio.h>_NEWLINE_ #include <stdlib.h>_NEWLINE_ _NEWLINE_ /* Let INFINITY be an integer value not likely to be   confused with a real weight, even a negative one. */_NEWLINE_ #define INFINITY ((cin << 14)-1)_NEWLINE_ _NEWLINE_ typedef struct {_NEWLINE_    int source;_NEWLINE_    int dest;_NEWLINE_    int weight;_NEWLINE_ } Edge;_NEWLINE_ _NEWLINE_ void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)_NEWLINE_ {_NEWLINE_    int *distance = (int*) malloc(nodecount * sizeof(*distance));_NEWLINE_    int i, j;_NEWLINE_    for (i=0; i < nodecount; i++)_NEWLINE_      distance[i] = INFINITY;_NEWLINE_ _NEWLINE_    /* The source node distance is set to zero. */_NEWLINE_    distance[source] = 0;_NEWLINE_ _NEWLINE_    for (i=0; i < nodecount; i++) {_NEWLINE_        for (j=0; j < edgecount; j++) {_NEWLINE_            if (distance[edges[j].source] != INFINITY) {_NEWLINE_                int new_distance = distance[edges[j].source] + edges[j].weight;_NEWLINE_ _NEWLINE_                if (new_distance < distance[edges[j].dest])_NEWLINE_                  distance[edges[j].dest] = new_distance;_NEWLINE_            }_NEWLINE_        }_NEWLINE_    }_NEWLINE_ _NEWLINE_    for (i=0; i < edgecount; i++) {_NEWLINE_        if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {_NEWLINE_            puts("Negative edge weight cycles detected!");_NEWLINE_            free(distance);_NEWLINE_            return;_NEWLINE_        }_NEWLINE_    }_NEWLINE_ _NEWLINE_    for (i=0; i < nodecount; i++) {_NEWLINE_        printf("The shortest distance between nodes %d and %d is %d\\n",_NEWLINE_            source, i, distance[i]);_NEWLINE_    }_NEWLINE_    free(distance);_NEWLINE_    return;_NEWLINE_ }_NEWLINE_ _NEWLINE_ int main(void)_NEWLINE_ {_NEWLINE_    /* This test case should produce the distances 2, 4, 7, -2, and 0. */_NEWLINE_    Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},_NEWLINE_                      {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},_NEWLINE_                      {4,0, 6}, {4,2, 7}};_NEWLINE_ _NEWLINE_    BellmanFord(edges, 10, 5, 4);_NEWLINE_ _NEWLINE_    return 0;_NEWLINE_ }'