Module: ダイクストラのアルゴリズム


Problem

1/14

ダイクストラ: 始まり (C++)

Theory Click to read/hide

n 個の頂点と m 個の辺を持つ有向または無向の重み付きグラフを指定します。すべてのエッジの重みは負ではありません。いくつかの開始頂点 s が指定されています。頂点 から他のすべての頂点までの最短パスの長さを見つけ、最短パスそのものを出力する方法も提供する必要があります。
 
この問題は「単一ソース最短経路問題」と呼ばれます。 (単一ソース最短経路問題)。

1-K BFS と同じタスクを実行しますが、K は関係ありません。また、1-K BFS と同様に、負のエッジを適切に処理しません。

アルゴリズム:
ダイクストラのアルゴリズム自体は N 回の反復で構成されます。次の反復では、頂点 V まだマークされていない頂点のうち、その頂点までの距離が最も小さい場合、この頂点がマークされ、そこから隣接する頂点の緩和が発生します。


 アルゴリズムの最終的な漸近動作は次のとおりです: O(n2+ m)

Problem

有向加重グラフが表示されます。指定された頂点から別の頂点までの最短距離を見つけます。
 
入力
最初の行には、N、S、F (1≤ N≤ 100、1≤ S、F≤ N) という 3 つの数値が含まれています。グラフの頂点の数、S -初期頂点と F –最後の。次の N 行に、それぞれ N 個の数字を入力します (100 を超えない)。グラフの重み隣接行列。-1 は頂点間にエッジがないことを意味し、負でない数値 –指定された重みのエッジの存在。ゼロは行列の主対角に書き込まれます。
 
出力
希望の距離を表示するか、指定した頂点間にパスがない場合は -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!