[C/C++]Dijkstra

0

Witam,

Mam pewien problem z zadaniem. Otóż polega on na znalezieniu w danym grafie najkrótszej ścieżki pomiędzy źródłem (source w kodzie), a wierzchołkiem docelowym (target).
Posiadałem już wcześniej algorytm Dijkstry, który nieco zmodyfikowałem do tego zadania. Jednak problem polega na tym, że zwraca minimalnie złą odpowiedź. Dla danych wejściowych:
8 15
1 2 5
1 3 4
2 3 2
2 3 5
2 6 5
3 5 3
3 4 4
3 6 6
4 6 5
4 7 5
4 8 4
5 6 4
5 7 7
6 7 5
7 8 4
2
1 7
2 2

Poprawne wyjścia to:
13
0

Mój program, jednak daje odpowiedzi: 12 i 0. Nie mam pojęcia skąd ten błąd w pierwszej, wydaje mi się, że wszystko jest prawidłowo zrobione.

Jeśli ktoś byłby uprzejmy i rzucił okiem na mój kod, będę wdzięczny :).

#include<queue>
#include<cstdio>
#include<vector>
#include<math.h>
using namespace std;

#define MAXINT (int)(pow(2,31)-1)
#define MAXV 10000


int G[MAXV][MAXV];
int total;

int dist[MAXV];
int parent[MAXV];
bool visited[MAXV];

void dijkstra(int s)
{
  priority_queue<pair<int,int> >Q;
  pair<int,int>nodes;
  int i,j;

  for (int i=0; i<total;++i) {
    dist[i]=MAXINT;
    parent[i]=-1;
    visited[i]=false;
  }

  dist[s]=0;
  Q.push(pair<int,int>(dist[s], s));

  while(!Q.empty()) {
    nodes=Q.top();
    Q.pop();
    i=nodes.second;
    if(!visited[i]) {
      visited[i]=true;
      for (j=0;j<total;++j)
        if(!visited[j] && G[i][j]>0 && dist[i]+G[i][j]<dist[j]) {
          dist[j]=dist[i]+G[i][j];
          parent[j]=i;
          Q.push(pair<int,int>(-dist[j],j));
        }
    }
  }
}

void findPath(int end,int c) {
    int weight=0;
  while (parent[end]!=-1) {
      weight+=c;
    end=parent[end];

  }
  printf("%d\n",weight);
}

int main()
{
   int a, b, c,il,source,target;
   int m;
   scanf("%d %d",&total, &m);
   for (int i=0;i<m;++i) {
     scanf("%d %d %d",&a, &b, &c);
     G[a][b]=c;
   }

   scanf("%d",&il);
   for(int i=0;i<il;++i){
      scanf("%d %d",&source, &target);
           dijkstra(source);
           findPath(target,c);
   }
   return 0;
}
0

Procedura findPath jest bez sensu. Czy zamiast niej nie powinieneś napisać czegoś w stylu: printf("%d\n", dist[target]); ?

0

Masz racje, teraz wszystko działa :). Dziękuje.
Jeszcze mam dwa pytania odnośnie algorytmu Dijkstry - czy np. po dodatni zmiennej d, która oznaczac będzie koszt drogi między wierzchołkami v ->u, moge to zapisać jako G[b][a]=d?
A drugie to, jak wykorzystać ten algorytm do przeszukiwania grafu w celu znalezienia dowolnej, najkrótszej ścieżki od wierzchołka wejściowego do wejściowego (:P). Chodzi o to, żeby algorytm startował ze źródła w 1, znajdował dowolną najkrótszą trase i wracał do 1, sumując po drodze wagi.

0

Odnośnie drugiego pytania to możesz zrobić w następujący sposób:
Liczysz najkrótsze ścieżki ze źródła do pozostałych i potem dla każdego wierzchołka sprawdzasz czy istnieje krawędź z tego wierzchołka do źródła, jeżeli tak to sumujesz koszt przejazdu ze źródła do danego wierzchołka i koszt tej krawędzi. Oczywiście bierzesz minimum z tych wszystkich wartości.

0

Najkrótsza ścieżka z wierzchołka wejściowego do wejściowego to raczej ścieżka zerowa ;] Ewentualnie możesz np na początek wrzucić do kolejki sąsiadów wierzchołka wejściowego (tzn tych do których są ścieżki), bez samego wierzchołka wejściowego. Wtedy znajdziesz najkrótszą niezerową ścieżkę.

Może chodziło ci o ścieżkę z wierzchołka docelowego do wierzchołka źródłowego. W takim przypadku po prostu w pętli while w findPath po prostu wypisuj wartość end.

Jeśli chcesz znaleźć wagę ścieżki sumując wagi połączeń to w findPath zamiast weight += c daj coś na wzór weight += G[parent[end]][end]. Parametr int c jest tam niepotrzebny.

0

To, że ścieżka od X do X wynosi 0 to wiem. Chodzi mi o coś innego - mianowicie, że wierzchołek początkowy jest równy końcowemu. Załóżmy, że mam graf V=3, E=3
1->2 koszt 4
2->1 koszt 3
2->3 koszt 4
3->2 koszt 2
1->3 koszt 1
3->1 koszt 1

I teraz chce znaleźć dowloną najkrótszą droge z wierzchołka 1 przez najkrótsze drogi i wrócić do punktu startowego.
Hm, czy tu bardziej cykl Eulera pasuje?

0

Cykl Eulera chyba przechodzi każdą ścieżkę dokładnie raz.

To co ty chcesz osiągnąć to chyba problem komiwojażera.

Opisz swój problem bardziej po polsku ;)

ATSD:
Ten graf co podałeś jest V=3, E=6 (3 wierzchołki, 6 krawędzi).

0

@vax samo stwierdzenie czy graf na cykl Hamiltona (cykl przechodzący przez wszystkie wierzchołki i wchodzący do każdego tylko raz) jest dość trudne (nie ma żadnego WKW na to, tylko warunki wystarczające), a szukanie dodatkowo najkrótszego takiego cyklu to już jest troche osłabiony (bo nie koniecznie masz tutaj graf pełny) komiwojażer jak już @donkey7 wspomniał, więc niestety ale ślepa uliczka ;)

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