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

از 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/]