Path with pre-determined size in a graph

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:05:05
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя aajjbb

Path with pre-determined size in a graph

Автор aajjbb, 12 лет назад, По-английски

Hi, is it possible to check if there's a path with size from a node 'a' to a node 'b' with size 'N' ? I've tried an BFS approach, using the 'visited' array with integer with a limit in the number 'N', but this strategy didn't worked.

Do you have any idea, or there's a well known algorithm for this ? (I seached, but didn't found anything)

graph

aajjbb
12 лет назад
25

Комментарии (25)

Написать комментарий?

riadwaw

12 лет назад, # |

← Rev. 2 →

O(m) solution for unweighted (__UPD:__ and undirected) graph:
Idea: if three its path of length t, there is path of length t+2(go somewhere and return). Let's find shortest path of length of parity of n. Create vertices (v,0), (v,1) for vertex v, edges (x,0)-(y,1) and (x,1)-(y,0) for edge x-y. Now go bfs from (a,0) to (b, n%1)

→ Ответить

aajjbb

12 лет назад, # ^ |

I didn't got it, if I want to travel from vertex 1 to vertex N in a path of M steps, how would I create this vertexes (v, 0), (v, 1) and this edges.

→ Ответить

wackloner

12 лет назад, # ^ |

Can we visit same vertex twice?

→ Ответить

aajjbb

12 лет назад, # ^ |

yes.

→ Ответить

wackloner

12 лет назад, # ^ |

← Rev. 2 →

Then you need to find shortest path with BFS (let it be d). If d <= m && d % 2 == m % 2, then answer YES, else NO. Why is it so? Shortest path a -> b at the end has some edge (v, a) and if d < m you can go by edge (a, v) and then again by edge (v, a), what results in d = d + 2. So you need to do it while d < m and if parity of d and m are the same, you have answer, otherwise — no.

→ Ответить

aajjbb

12 лет назад, # ^ |

← Rev. 4 →

I've already tried it and didn't worked.. but I'm almost sure this strategy is right. EDIT: My strategy it this one:


#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string.h>
#include <stdio.h>

using namespace std;

const int INF = 100000000;
int c, l, a, b, s, e, d, maze[110][110], dist[110], vis[110];

int main(void) {
    while(cin >> c >> l && !(c == 0 && l == 0)) {
        memset(maze, 0, sizeof(maze));
        for(int i = 0; i <= c; i++) {
            dist[i] = INF;
            vis[i] = 0;
        }
        for(int i = 0; i < l; i++) {
            cin >> a >> b;
            maze[a][b] = maze[b][a] = 1;
        }
        cin >> s >> e >> d;
        if(d == 0 && s == e || (s == e && d == 1)) {
            cout << "Yes, Teobaldo can travel." << endl;
            continue;
        }
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        dist[s] = 0;
        while(!q.empty()) {
            int tmp = q.front(); q.pop();
            for(int i = 1; i <= c; i++) {
                if(maze[tmp][i] == 1 && !vis[i]) {
                    dist[i] = dist[tmp] + 1;
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
        if(dist[e] <= d && dist[e] % 2 == d % 2 && !(c == 1 && l == 0 && s == 1 && e == 1 && d != 0) && d != 0) {
            cout << "Yes, Teobaldo can travel." << endl;
        } else {
            cout << "No, Teobaldo can not travel." << endl;
        }
    }
    return 0;
}

→ Ответить

wackloner

12 лет назад, # ^ |

← Rev. 2 →

Lets look.

→ Ответить

aajjbb

12 лет назад, # ^ |

yes, it's unoriented and unweighted, by the way here's the link, the statement is in portuguese but google translate make a good job Link

→ Ответить

wackloner

12 лет назад, # ^ |

Problem in your BFS, you should mark vertex as visited when you look at that not when you get there by bfs. So it must look like something that:

while(!q.empty()) {
  int tmp = q.front(); q.pop();
  for(int i = 1; i <= c; i++) {
    if(maze[tmp][i] == 1 && !vis[i]) {
      dist[i] = dist[tmp] + 1;
      vis[i] = 1
      q.push(i);
    }
  }
}

→ Ответить

aajjbb

12 лет назад, # ^ |

I've already tried this strategy, and didn't worked again.

→ Ответить

wackloner

12 лет назад, # ^ |

Did you process case when c = 1, l = 0, s = 1, e = 1, d <> 0?

→ Ответить

aajjbb

12 лет назад, # ^ |

Yes, and it's yet a WA.I can't see one error in this approach. The update code is in the previous comment.

→ Ответить

wackloner

12 лет назад, # ^ |

← Rev. 2 →

Oh, sorry, man, i've just got, that my solution was wrong. And riadwaw was right: you need to make graph with vertices (v, p) where v is number and p is parity. In this graph you need to find shortes path (s, 0) -> (e, d % 2) . And if it exist you have answer YES otherwise — NO. Don't forget about case where s == e d != 1 and you haven't got any edge from s.

→ Ответить

aajjbb

12 лет назад, # ^ |

Oh, It was another corner case I was forgetting, but it's yet WA. I've also got another corner, when 'd == 0' there's no possible path since for only being in the starter vertex, it's already count as one node in the path. The new code is in the previous comment.

→ Ответить

aajjbb

12 лет назад, # ^ |

I didn't got it yet, I should BFS through pairs ? with a starter vertex (s, 0) ? how would I relax it's distance ?

→ Ответить

bharatkulratan

12 лет назад, # |

It's a undirected and unweighted graph. Build an adjacency matrix for this graph. Raise this square matrix up to the power 'N' and check if the adj[a][b] > 0 because doing so gives you the number of different paths of length N in adj[a][b]. Obviously if adj[a][b] > 0 holds true, there is a path between these two nodes. For multiplication of matrix N times, you could use fast matrix multiplication technique.

→ Ответить

riadwaw

12 лет назад, # ^ |

It should work with directed graphs to.

You may use "and" instead of multiplication and "or" instead of sum to avoid overflow

→ Ответить

aajjbb

12 лет назад, # ^ |

To make the multiplication for N I should do adj[i][j] ^ N isn't it ? using and and or to avoid overflow, it would be adj[i][j] & N ?

→ Ответить

aajjbb

12 лет назад, # ^ |

I'm looking for matrix multiplication techniques now. s

→ Ответить

wackloner

12 лет назад, # ^ |

With trivial multiplication of matrices you get solution for O(c^3*logd), which is good. So you need just to write function binPow for matrices with trivial multiplication.

→ Ответить

aajjbb

12 лет назад, # ^ |

← Rev. 2 →

I'm yet a newbie in matrix operations, just googling for 'binPow' I've found it, is the definition of the function right ? Link

→ Ответить

wackloner

12 лет назад, # ^ |

Yeah, its right. If you want and if it helps you, you can check my code for this problem.

→ Ответить

aajjbb

12 лет назад, # ^ |

Thank you, I finally got 'AC', I'm still curious how this matrix multiplication find this paths, I'll study more on matrix operations, search more for this problem on the net, I've found this solution which get 'AC' too, LINK. it looks like a weird BFS, but the code is too messy, so it made me more sure that there's also a 'graph' solution(which doesn't use matrix multiplication) to solve this problem.

→ Ответить

Petar

12 лет назад, # ^ |

There is a theorem in Graph theory which states: Consider a graph G with n vertices, consider its adjacency matrix, call it A. Now consider a natural number, like x. Raise A to the power of x to obtain A^x. Then, for each i and j, entry A^x(i, j) contains number of walks from vertex i to vertex j. It can be proved using induction on x. Note that we're calculating it using Dynamic Programming. Base case is trivial, for induction step, consider all walks of length x+1 from i to j. Now consider vertex before j in our walk. Call it u. Obviously, for each u, number of walks of length x+1 from i to j equals to number of walks of length x from i to u, multiplied by number of walks of length 1 from u to j (That is, if they're adjacent in G). By multiplying A^x * A, we're calculating all such walks. Hence we're done. Note : Refer to definition of matrix multiplication for understanding induction step efficiently.

→ Ответить

aajjbb

12 лет назад, # ^ |

Thank you so much, now I've got this approach, but I'll keep studying on matrix multiplication.. but did you saw the code I've paste in the last comment, it looks like a bfs, but the author make so weird stuff inside it, but it made me thought that there's also a solution using BFS. do you know these solution too ?

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 18:29:56 (i2).

Десктопная версия, переключиться на мобильную.

При поддержке