Module: Dijkstra'nın algoritması


Problem

1/14

Dijkstra: Başlangıç ​​(C++)

Theory Click to read/hide

n köşeli ve m kenarlı, yönlü veya yönsüz ağırlıklı bir grafik verildi. Tüm kenarların ağırlıkları negatif değildir. Bazı başlangıç ​​tepe noktaları belirtilmiştir. Köşe noktalarından diğer tüm köşelere giden en kısa yolların uzunluklarını bulmanız ve ayrıca en kısa yolları kendilerinin yazdırması için bir yol sağlamanız gerekir.
 
Bu soruna "tek kaynaklı en kısa yol sorunu" denir (tek kaynaklı en kısa yollar sorunu).

1-K BFS ile aynı görevleri gerçekleştirir, ancak K'yi dikkate almaz. Ayrıca, 1-K BFS gibi, negatif kenarları düzgün bir şekilde işlemez

Algoritma:
Dijkstra'nın algoritmasının kendisi N yinelemeden oluşur. Bir sonraki yinelemede, tepe noktası V  henüz işaretlenmemiş köşelerden ona en küçük mesafe ile, bu köşe işaretlenir ve komşu köşelerde ondan gevşemeler meydana gelir.


 algoritmanın nihai asimptotik davranışı: O(n2+ m)

Problem

Size yönlendirilmiş ağırlıklı bir grafik verilir. Belirli bir köşeden diğerine en kısa mesafeyi bulun.
 
Giriş
İlk satır üç sayı içerir: N, S ve F (1≤ N≤ 100, 1≤ S, F≤ N), burada N – grafik köşe sayısı, S – ilk tepe noktası ve F –ndash; son. Sonraki N satırın her birine 100'ü geçmeyecek şekilde N sayı girin, – grafiğin ağırlık bitişik matrisi, burada -1, köşeler arasında kenar olmaması ve negatif olmayan herhangi bir sayı anlamına gelir -ndash; verilen ağırlıkta bir kenarın varlığı. Matrisin ana köşegenine sıfırlar yazılır.
 
Çıktı
İstenilen mesafenin veya belirtilen köşeler arasında yol yoksa -1 gösterilmesi gerekir.

Örnekler

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++
# Girdi Çıktı
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!