Module: Dijkstra의 알고리즘


Problem

1/14

다익스트라: 더 비기닝(C++)

Theory Click to read/hide

<사업부>

n개의 꼭지점과 m개의 가장자리가 있는 유향 또는 무향 가중 그래프가 주어집니다. 모든 간선의 가중치는 음수가 아닙니다. 일부 시작 정점 s가 지정됩니다. 정점 s에서 다른 모든 정점까지의 최단 경로 길이를 찾고 최단 경로 자체를 인쇄하는 방법도 제공해야 합니다.
 
이 문제를 "단일 소스 최단 경로 문제"라고 합니다. (단일 소스 최단 경로 문제).

1-K BFS와 동일한 작업을 수행하지만 K에 관계없이 수행합니다. 또한 1-K BFS와 마찬가지로 음수 에지를 제대로 처리하지 않습니다.
<사업부>
알고리즘:
Dijkstra의 알고리즘 자체는 N 반복으로 구성됩니다. 다음 반복에서 정점 V  아직 표시되지 않은 꼭짓점 중에서 가장 짧은 거리로 이 꼭짓점이 표시되고 인접 꼭지점의 이완이 발생합니다.
<사업부>

 알고리즘의 최종 점근적 동작: O(n2+ m)

Problem

방향 가중치 그래프가 제공됩니다. 주어진 정점에서 다른 정점까지의 최단 거리를 찾습니다.
 
입력
첫 번째 줄에는 N, S 및 F(1≤ N≤ 100, 1≤ S, F≤ N)의 세 가지 숫자가 포함되어 있습니다. 그래프 정점의 수, S – 초기 정점 및 F – 결정적인. 다음 N 줄에 각각 100을 넘지 않는 N개의 숫자를 입력하세요. – 그래프의 가중치 인접 행렬, 여기서 -1은 정점 사이에 가장자리가 없고 음수가 아닌 숫자를 의미합니다. 주어진 가중치의 가장자리가 존재합니다. 0은 매트릭스의 주대각선에 기록됩니다.
 
출력
지정된 꼭짓점 사이에 경로가 없으면 원하는 거리 또는 -1을 표시해야 합니다.

예 <헤드> <일># <몸>

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
3 2 1
<사업부>0 1 1
4 0 1
2 1 0
 3
Write the program below 
#include<iostream>
 
using namespace std;
 
int main()
{
    const int N1 = 110;
    int N, S, F, g[N1][N1], i, j, mini, d[N1];
    bool used[N1];
   
    cin >> N >> S >> F;
   
    fill(used, used + N, false);
   
    fill(d, d + N, 10000000);
   
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            cin >> g[i][j];
    }
   
    d[S - 1] = 0;
   
    for (i = 0; i < N; i++)
    {
        mini = -1;
       
        for (j = 0; j < N; j++)
        {
            if (!used[j] && (mini == -1 || d[j] < d[mini]))
                mini = j;
        }
       
        used[mini] = true; 
    if (d[F - 1] == 10000000)
        cout << "-1";
    else
        cout << d[F - 1];
}

     

Program check result

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