Module: الگوریتم دایکسترا


Problem

1/14

Dijkstra: The Beginning (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)، که در آن N – تعداد رئوس نمودار، S – راس اولیه، و F – نهایی در N سطر بعدی، هر کدام N عدد را وارد کنید که از 100 تجاوز نکند، – وزن ماتریس مجاورت نمودار، که در آن -1 به معنای عدم وجود لبه بین رئوس و هر عدد غیر منفی است – وجود لبه با وزن معین صفرها روی قطر اصلی ماتریس نوشته می شوند.
 
خروجی
اگر مسیری بین رئوس مشخص شده وجود نداشته باشد، باید فاصله مورد نظر یا -1 نمایش داده شود.

نمونه‌ها <سر> <بدن>
# ورودی خروجی
1
3 2 1
0 1 1
4 0 1
2 1 0
 3

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++
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!