This wiki has no edits or logs made within the last 45 days, therefore it is marked as inactive. If you would like to prevent this wiki from being closed, please start showing signs of activity here. If there are no signs of this wiki being used within the next 15 days, this wiki may be closed per the Dormancy Policy. This wiki will then be eligible for adoption by another user. If not adopted and still inactive 135 days from now, this wiki will become eligible for deletion. Please be sure to familiarize yourself with Miraheze's Dormancy Policy. If you are a bureaucrat, you can go to Special:ManageWiki and uncheck "inactive" yourself. If you have any other questions or concerns, please don't hesitate to ask at Stewards' noticeboard.

پیدا کردن دور منفی در گراف

از shaazzz
پرش به ناوبری پرش به جستجو

پیدا کردن دور منفی در گراف[ویرایش]

یک گراف جهت دار و وزن دار با N راس و M یال داریم و می خواهیم اگر گراف مان دارای دور منفی(دوری که مجموع وزن یال های آن منفی باشد) بود ، آن را پیدا کنیم. اگر از نگاه دیگری به مساله نگاه کنیم میتوان پرسید که دور با یک وزن کوچک دلخواه را پیدا کنید و همچنین رئوس این دور را هم بگویید. راه حل های متفاوتی برای حل این دو مساله وجود دارد که ما در این جا راجع به آن ها توضیح خواهیم داد.

استفاده از الگوریتم بلمن فورد[ویرایش]

با استفاده از الگوریتم بلمن فورد میتوان وجود دور منفی در گراف را بررسی کرد و اگر این دور وجود داشت ، یکی از آن ها را پیدا می کند.

جزئیات این الگوریتم را می توانید در قسمت بلمن فورد بخوانید. در اینجا فقط به کاربرد این الگوریتم در این مساله می پردازیم.

N بار الگوریتم بلمن فورد را روی گراف اجرا می کنیم. اگر تغییری در آخرین مرحله نبود یعنی دور منفی نداریم. در غیر این صورت راسی را که مسیر رسیدن به آن تغییر کرده ، انتخاب می کنیم و با استفاده از پدرهایش به عقب باز میگردیم تا دور مورد نظر را پیدا کنیم.

پیاده سازی[ویرایش]

struct Edge {
    int a, b, cost;
};

int n, m;
vector<Edge> edges;
const int INF = 1000000000;

void solve()
{
    vector<int> d(n);
    vector<int> p(n, -1);
    int x;
    for (int i = 0; i < n; ++i) {
        x = -1;
        for (Edge e : edges) {
            if (d[e.a] + e.cost < d[e.b]) {
                d[e.b] = d[e.a] + e.cost;
                p[e.b] = e.a;
                x = e.b;
            }
        }
    }

    if (x == -1) {
        cout << "No negative cycle found.";
    } else {
        for (int i = 0; i < n; ++i)
            x = p[x];

        vector<int> cycle;
        for (int v = x;; v = p[v]) {
            cycle.push_back(v);
            if (v == x && cycle.size() > 1)
                break;
        }
        reverse(cycle.begin(), cycle.end());

        cout << "Negative cycle: ";
        for (int v : cycle)
            cout << v << ' ';
        cout << endl;
    }
}

استفاده از الگوریتم فلوید وارشال[ویرایش]

از الگوریتم فلوید وارشال برای حل مساله دوم استفاده خواهیم کرد. یعنی پیدا کردن هر دو راس (i , j) که مسیر بین آن ها از مقدار مشخصی کمتر نیست.

الگوریتم فلوید وارشال را روی گراف اجرا میکنیم و به ازای هر راس v در گراف داریم 0 = [d[v][v . اگر بعد از اجرای الگوریتم این مقدار برای راس x منفی بود ، یعنی یک دور منفی از x به x وجود دارد. از همین روش میتوان فهمید که بین دو راس ، کوتاه ترین مسیر وجود دارد یا نه. به این صورت که از یک راس دیگری مانند t که احتمال می رود در مسیر بین j , i باشند ، استفاده میکنیم(در واقع باید تمام رئوس را به جای t قرار دهیم. آنگاه کوتاه ترین مسیر از i به j وجود ندارد اگر راسی مانند t باشد که d[t][t] < 0 (یعنی در یک دور منفی باشد) و بتوان از i به t و از t به j رسید که در این صورت d[i][j] = -INF می شود(یعنی کوچکترین عدد ممکن).


پیاده سازی[ویرایش]

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        for (int t = 0; t < n; ++t) {
            if (d[i][t] < INF && d[t][t] < 0 && d[t][j] < INF)
                d[i][j] = - INF; 
        }
    }
}

مسائل تمرینی[ویرایش]

[UVA: Wormholes https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499] [SPOJ: Alice in Amsterdam, I mean Wonderland https://www.spoj.com/problems/UCV2013B/] [SPOJ: Johnsons Algorithm https://www.spoj.com/problems/JHNSN/]