Tag: Algorithms

I have a problem as below and I am really stuck with it as it run with more than the time I desired (about 1 second). I really want your help to build up a more efficient algorithms than mine

Given an undirected graph G = (V, E) with two parameter of weights w1 and w2 for each edges. This graph has N vertices and M edges. A K-Elementary path S is a sub-graph of G which must be an elementary graph and it does have exactly K edges.

Find a K-elementary path S with the sum of w1 of all edges as minimum value and the sum of w2 of all edges of S must be smaller than a given value Q. If it does not exist any path satisfied, print out the value -1

Input:

The first line with four values N, M, K, Q (2 <= N, K <= 50, 1 <= M <= 2*N, 1 <= Q <= 10^9)

The next M lines show the edges of the graph: V1 V2 W1 W2 (1 <= V1, V2 <= N, 1 <= W1 <= 10^4, 1 <= W2 <= 10^4)

Output: One integer to show the minimum weight of the k-elementary graph found. -1 if non-exists

Sample test case:

Input:

5 7 3 6
1 2 1 2
1 4 2 2
1 5 3 6
2 3 3 2
2 4 4 4
3 4 5 1
4 5 4 7

Output:

6

First of all, I want to quote the definition of an elementary path.

In short, for this problem, we need to find an k-elementary path S such that the weight to w1 is minimum, the sum of all edges to w2 is less than or equal to Q and it does have exactly K edges.

I do have a Backtracking approach, in which I tried to build up all the graph satisfying the second condition (w2) and then find the minimum of the first condition (w1) but, as you have known, the time complexity is quite high. However, I find it hard to convert it to dynamic programming or any other methods to reduce to time complexity. I do add some Branch-bound condition but it is still slow.

Below is my source code which you can refer but I do not think it is useful

#include <bits/stdc++.h>
using namespace std;
#define N 51
#define INF 1e9
int n, m, K, Q;
bool appear(N);
int W1(N)(N);
int W2(N)(N);
int currentSum1 = 0;
int currentSum2 = 0;
int source = 0;
int res = INF;
int Log(N);
int minElement = INF;
bool check(int k, int v)
{
    return !appear(v) && W1(Log(k - 1))(v) != 0 && W2(Log(k - 1))(v) != 0;
}
void solution()
{
    if(currentSum1 != 0 && currentSum1 < res)
    {
        res = currentSum1;
        // for(int i = 0; i <= K; i++)
        //     cout << Log(i) << " ";
        // cout << endl;
    }
}
void solve(int k)
{
    for(int v = 1; v <= n; v++)
    {
        if(check(k, v) && currentSum2 + W2(source)(v) <= Q && currentSum1 + (K - k) * minElement <= res) //Branch-bound condition
        {
            Log(k) = v;
            currentSum2 += W2(Log(k - 1))(v);
            currentSum1 += W1(Log(k - 1))(v);
            appear(v) = true;
            if(k == K)
                solution();
            else
                solve(k + 1);
            currentSum1 -= W1(Log(k - 1))(v);
            currentSum2 -= W2(Log(k - 1))(v);
            appear(v) = false;
        }
    }
}
int main()
{
    fast;
    // freopen("data.txt", "r", stdin);
    cin >> n >> m >> K >> Q;
    for(int i = 0; i < m; i++)
    {
        int x, y, w1, w2;
        cin >> x >> y >> w1 >> w2;
        minElement = min(minElement, w1);
        W1(x)(y) = w1;
        W1(y)(x) = w1;
        W2(x)(y) = w2;
        W2(y)(x) = w2;
    }
    for(int v = 1; v <= n; v++)
    {
        source = v;
        currentSum2 = 0;
        currentSum1 = 0;
        Log(0) = v;
        for(int i = 1; i <= n; i++)
            appear(i) = false;
        appear(source) = true;
        solve(1);
    }
    if(res != INF)
        cout << res << endl;
    else 
        cout << -1 << endl;
}