wyszukiwanie polaczen

Witam,
pisze program który mam wyszukiwać połączenia miedzy jakimiś wierzchołkami grafu ważonego. Chodzi o to ze mam jakiś graf, który jest mapą i na podstawie tego grafu tworze jakieś trasy np. pociągów, których przystankami są wierzchołki tego grafu.
W programie tworzę sobie kilka linii przejeżdżających przez różne wierzchołki tego grafu (niektóre się pokrywają). Jaki algorytm zastosować mam do wyszukania połączenia od wierzchołka x do wierzchołka y ?

Algorytm Dijkstry lub Bellmana-Forda. Oba służą do wyznaczania najkrótszej ścieżki w grafie ważonym.

Ale ja nie szukam ścieżek w grafie tylko w trasach, które nie są grafem.

No to czemu nie stworzysz z tych tras grafu i nie użyjesz np. wcześniej wspomnianej Dijkstry?

To jest chyba spore uproszczenie ułatwienie,a przecież w rzeczywistości wierzchołki początkowe nie będą miały wierzchołka poprzedniego, a końcowe wierzchołka następnego.

Mój problem przedstawia poniższy schemat:

Dalej nie rozumiem jaki jest problem ze stworzeniem grafu z tych tras. Robisz listę sąsiedztwa i odpalasz dijkstre. Chyba ze nie widzę czegoś oczywistego

Czyli z grubsza mam utworzyć Listę pociągów. Każdy pociąg będzie zawierał listę przystanków. Wyszukując drogę od X do Y sprawdzam które pociągi zawierają te przystanki i później z pociągów które zawierają te przystanki wybieram pociąg który ma najkrótszą odległość od X do Y. Przepraszam ale jestem początkujący. Mógłbyś potwierdzić to co napisałem?

Aha no to wiem już chyba jak dokładnie opisać swój problem. Algorytm djikstry wyszukuje mi najkrótszą drogę od punktu A do punktu B w grafie ważonym. Co będzie w przypadku gdy pociąg nie będzie jechał najkrótszymi drogami?

No i czy na pewno algorytm Djikstry będzie miał zastosowanie tutaj, przecież Linie nie tworzą grafu. Graf jest zawsze zamknięty.

No ale linie tworzą jakiś swój graf. I na tym grafie, który opisuje Linie odpalasz dijkstrę, a nie na głównym grafie ze wszystkimi wierzchołkami

Dokladnie tak chce zrobić , ale przecież te Linie nie tworzą grafu, bo nie zamykają się.

Może zacznij od opisania problemu jaki rozwiązujesz.

• planowanie tras pociągów?
• planowanie podróży między stacjami?
• planowanie odwiedzenia wszystkich stacji (problem komiwojażera)

Na 99% masz problem opisywany grafem, tylko że źle projektujesz ten graf (na złych danych).

Mam problem z wyszukiwaniem połączeń od wierzchołka X do wierzchołka Y. Graf wczytuje w następujący sposób:

• wierzchołek A, współrzędne(x,y), wierzchołek B, współrzędne(x,y),
  itd.
  Współrzędne są mi potrzebne do wyliczenia odległości (wagi).
  Później wprowadzam jakieś linie na ten graf w postaci:
• numer linii, tablica wierzchołków (przystanków)
  No i teraz jak już mam jakieś linie na tym grafie to chce wyszukać jakieś linie z drogą od jakiegoś punkt X do Y no i z tych linii wybrać tą która jest najkrótsza.

Mały Orzeł napisał(a):

ale przecież te Linie nie tworzą grafu, bo nie zamykają się.

Nie zamykają się to znaczy, że nie są cyklem? To co, że nie są cyklem. To raczej nic nie zmienia.

Może to coś pomoże. Mogło by to wyglądać np. tak:

 
	const size_t maxW = 100;
	const size_t maxH = 100;
	
	vector< vector< int > > graf( maxH, vector< int >( maxW, -1 ) );
	vector< StrukturaWierzcholka > wierzcholki;
	
	//tu zrob wczytywanie wierzcholkow...
	
	//wczytywanie linii
	while( jest linia do wczytania )
	{
		size_t linia;
		int wierzcholek = -1, poprzedniWierzcholek;
		
		cin >> linia;
		
		while( jest wierzcholek do wczytania )
		{
			poprzedniWierzcholek = wierzcholek;
			
			cin >> wierzcholek;
			
			if( poprzedniWierzcholek != -1 )
			{
				int odleglosc = obliczOdleglosc( wierzcholki[wierzcholek], 
												 wierzcholki[poprzedniWierzcholek] );
				
				graf[poprzedniWierzcholek][wierzcholek] = odleglosc;
				graf[wierzcholek][poprzedniWierzcholek] = odleglosc;
			}
		}
	}
	
	droga = dijkstra( wierzcholekA, wierzcholekB, graf );

Czyli tworzysz graf dla wierzchołków na podstawie wczytanych linii

A da się w tym kodzie zmienić ten kontener set na vector, czy lepiej pisać to od nowa?

 
#include<iostream>
#include<vector>
#include<set>
#include <cstdlib>

using namespace std;

const int infty = 1000000000; // uwaga na limit
int n,m;
vector< pair<int,int> > adj[100000];

vector<int> waga;

struct cmp
{
    // czy a jest mniejsze od b
    bool operator() (const int &a, const int &b)
    {
        if (waga[a] < waga[b]) return true;
        if (waga[a] > waga[b]) return false;
        return a<b;
    }
};


set<int, cmp> kopiec; // ;-)


void dijkstra(int s)
{
    int v, u, c;
    waga.clear(); // kasuje wektor
    waga.resize(n, infty); //

    waga[s] = 0;
    kopiec.clear();
    for (int i=0; i<n; i++) kopiec.insert(i);

    while( !kopiec.empty() )
    {
        u = *(kopiec.begin());
        kopiec.erase(kopiec.begin());

        for (int i=0; i<adj[u].size(); i++)
        {
            v = adj[u][i].first;
            c = adj[u][i].second;
            if (waga[u]+c < waga[v])
            {
                // uaktualniamy wagê wierzcho³ka v
                kopiec.erase(kopiec.find(v));
                waga[v] = waga[u]+c;
                kopiec.insert(v);
            }
        }
    }


}



int main(void)
{
    int a,b,c, s,t;

    cout <<"podaj ilosc wierzcholkow:\n";          //*
    cin >> n;
    cout <<"podaj ilosc krawedzi:\n";               //*
    cin >>m;


    for (int i=0; i<m; i++)
    {
        cout <<"\npodaj "<<i+1<<" pare wierzcholkow oraz wage krawedzi laczacej te wierzcholki:\n" ;  //*

        cin >> a >> b >> c;   // c = koszt krawêdzi od a do b

        adj[a].push_back( pair<int,int>(b,c) );
    }


    cout<<"\npodaj wierzcholki startowy i docelowy:";       //*
    cin >> s >> t; // s - Ÿród³o, t - wierzcho³ek, do którego najkrótszej odleg³oœci szukamy

    dijkstra(s); // alg. Dijkstry wype³ni ca³¹ tablicê waga[..] najkrótszymi odleg³oœciami

    cout<<"\ndlugosc najkrotszej sciezki:";     //*

    cout << waga[t];
    system("pause");                           //*
    return 0;
}

A co do tego twojego pseudokodu to jak będę identyfikował linie?