Wszystkie możliwe drogi.

0

Witam!

Mam problem z zadaniem, w którym muszę wypisać ilość możliwych dróg. Szczerze mówiąc, nie wiem nawet, jak się za to zabrać dopiero od tygodnia piszę w c++, wcześniej tylko PHP i RAMmachine. Na wejściu mamy x=ilości miast (miasta 1, 2, 3, ... , (x-1), x), y=ilości dróg, a później y dróg jednokierunkowych n m (z miasta n do miasta m). Między miastami może być więcej niż jedna droga. Wyjście to ilość możliwości dotarcia z miasta 1 do miasta 2, dla nieskończonej wypisujemy inf. Dróg można używać wielokrotnie. Czy moglibyście mi pomóc?

Przykład wejścia:

4 5
1 3
3 4
3 1
1 3
3 2

0

Teoria grafów: graf skierowany, szukanie ilości ścieżek z wierzchołka A do B.

0

Algorytmy grafowe.

0

Ok, znalazłem niezłego pdf-a, z którego przynajmniej coś rozumiem. Chciałem na początku stworzyć tablicę dwuwymiarową miasto*miasto, wyzerować ją i w pola w których jest droga wpisać ilość dróg. Nie mogę sobie poradzić z zerowaniem. Mój kod:
EDIT: zmieniłem to:

 
	do
		{
		do
			{
			ttwod[i][j]=0;
			j=j+1;
			}
			while (j==(!(lmiast+1)));

na to co jest w następnym poście. Zapomniałem o zmianie wartości drugiej zmiennej w pierwszym while'u.

0

Dobra, poradziłem sobie :)
Teraz kod wygląda tak:

#include <iostream>
using namespace std;
int main() {
	int lmiast, ldrog;
	cin >> lmiast;
	cin >> ldrog;
	int zmiasta, domiasta, x, y;
	int ttwod[(lmiast+1)][(lmiast+1)];
	x=0;
	y=0;
	while (!(x==(lmiast)))
		{
		y=0;
		while (!(y==(lmiast)))
			{
			ttwod[x][y]=0;
			y=y+1;
			}
		x=x+1;	
		} 
		x=(0);
	for (x=0; (!(x==ldrog)); x=x+1)
		{
		cin >> zmiasta;
		cin >> domiasta;
		ttwod[zmiasta][domiasta]=(ttwod[zmiasta][domiasta]+1);
		}
/* KONIEC TABLICY. CO DALEJ? */
}
 

Rozumiem, że dalej trzeba zastosować jakąś metodę poszukiwania ścieżek. Jaką według Was powinienem zastosować (albo przynajmniej spróbować:))?

1 użytkowników online, w tym zalogowanych: 0, gości: 1