Module: 포드-벨만 알고리즘


Problem

1/6

Ford-Bellman: 시작(C++)

Theory Click to read/hide

포드-벨만 알고리즘
n 꼭지점과 m 가장자리, 일부 시작 꼭지점 vG가 주어집니다. > . 정점 v에서 다른 모든 정점까지의 최단 경로 길이를 찾는 데 필요합니다.

Dijkstra와 마찬가지로 Ford-Bellman은 꼭지점 1에서 다른 모든 정점까지의 거리를 찾지만 음의 가장자리로 작동.
<사업부> 
Ford-Bellman 알고리즘 자체는 여러 단계(n-1)로 구성됩니다. 각 단계에서 그래프의 모든 가장자리가 검사되고 알고리즘은 비용 c의 각 가장자리 (a, b)를 따라 완화하려고 시도합니다. 가장자리를 따라 이완 — 이것은 d[a] 의 의미를 개선하려는 시도입니다. 값 d[b] + c. 사실 이것은 우리가 edge  상단에 대한 현재 답변입니다.

d 배열은 Dijkstra와 마찬가지로 시작 정점에서 가장 짧은 길이의 배열입니다. 처음에는 시작 정점을 제외하고 가능한 한 큰 숫자로 채웁니다. 0.
에지를 저장하기 위해 인접 행렬이나 가중치 행렬이 아니라 에지가 어느 노드에서 출발하는지(from), 어느 노드로 오는지(to) 및 무게(비용).
  구조체 가장자리 { int from, to, 비용; }; 벡터<에지> 가장자리;
INF 상수는 숫자 "무한대"를 나타냅니다. - 가능한 모든 경로 길이를 분명히 초과하는 방식으로 선택해야 합니다.
<사업부>
알고리즘의 가장 간단한 구현: d[v] = 0; for (int i=0; i

또는 C++11:
구문을 사용하여 조금 더 짧게   d[v] = 0; for (int i=0; i< n-1; ++i) for (에지 j: 에지) if (d[j.from] <INF) d[j.to] = min(d[j.to], d[j.from] + j.cost);

작업 예시


간단한 방향성 그래프를 가져옵니다.  5개의 노드, 가중치가 1인 4개의 에지.

그 순서대로 에지 목록을 소개하겠습니다.
4 5 1
3 4 1
2 3 1
1 2 1

최단 길이 배열의 초기 값:
  <몸>
여기서 inf는 항상 가장자리의 가중치보다 큰 일치하는 정수여야 합니다.

1차 합격 후
 
0 정보 정보 정보 정보
<몸>
2차 합격 후
 
0 1 정보 정보 정보
<몸>
3차 합격 후
 
0 1 2 정보 정보
<몸>

4차 통과 후
 
0 1 2 3 정보
<몸>
1에서 마지막 순서로 가장자리를 공급하면 첫 번째 통과 후 가장 짧은 길이를 찾을 수 있습니다.

 

Problem

프로그램을 완성하여 다음 문제를 올바르게 풀도록 하세요.

다중 에지와 루프를 가질 수 있는 유향 그래프가 주어집니다. 각 모서리에는 정수(음수일 수 있음)로 표시되는 가중치가 있습니다. 음수 가중치 주기가 없음을 보장합니다.
1번 정점에서 다른 모든 정점까지의 최단 경로 길이를 계산해야 합니다.
 
입력
프로그램은 먼저 숫자 N(1 <= N <= 100)을 수신합니다. 그래프 정점의 수와 숫자 M (0 <= M <= 10000) – 갈비뼈의 수. 다음 행에는 에지를 설명하는 세 개의 숫자로 구성된 M이 포함되어 있습니다: 에지의 시작, 에지의 끝 및 가중치(가중치 –는 -100에서 100까지의 정수임).< /사업부>
 
출력
프로그램은 N개의 숫자를 출력해야 합니다 – 정점 번호 1에서 그래프의 모든 정점까지의 거리. 해당 정점에 대한 경로가 없으면 경로의 길이 대신 숫자 30000을 인쇄하십시오.
 
예
0 1 2 3 4
<헤드> <일># <몸>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
입력 출력
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 
Write the program below 
#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

struct edge
{
    int from, to, w;
};

vector <edge> edges;
int d[201];

int main()
{
    int n, m, from, to, w;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < m; i++)
    {
        edge e;
        cin >> e.from >> e.to >> e.w;
        edges.push_back(e);
    }

    d[1] = 0;

    for (int i = 1; i < n; i++)
    {         
    }

    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
            cout << 30000 <<" " ;
        else
            cout << d[i] << " ";
    }

    return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!