Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

graf- jak go usprawnić?

Ostatnio zmodyfikowano 2015-06-06 18:01
Autor Wiadomość
radioactive15
Temat założony przez niniejszego użytkownika
graf- jak go usprawnić?
» 2015-06-06 17:10:11
Witam!
Proszę o pomoc w usprawnieniu kodu, tak aby program znalazł najszybszą drogę z pierwszego wierzchołka do każdego innego. Jestem początkująca i nie do końca wiem jak to zrobić :)

Kod źródłowy:
C/C++
#include <stdio.h>
#include <iostream>
#define n 8
#define INF 9999999
using namespace std;

int W[ n ][ n ] = { // Macierz sąsiedztwa opisująca graf
    { 0, 5, 0, 0, 10, 0, 11, 0 },
    { 0, 0, 1, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 1, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 0, 0 },
    { 3, 2, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0, 2 },
    { 0, 0, 0, 2, 0, 0, 0, 0 },
    { 0, 0, 5, 0, 7, 0, 1, 0 } };
int Q[ n ] = { 1, 1, 1, 1, 1, 1, 1, 1 }; // Zbiór wuierzchołków do przetworzenia
int D[ n ] = { INF, INF, INF, INF, INF, INF, INF, INF }; // Tablica odległości od s
int P[ n ] = { - 1, - 1, - 1, - 1, - 1, - 1, - 1, - 1 }; // Tabela poprzedników

void Dijkstra( int s ) {
    int u, v; // Obsługiwane wierzchołki
    int Dmin;
   
    D[ s ] = 0;
   
    do {
        Dmin = INF;
        for( v = 0; v < n; ++v ) // Szukamy takiego wierzchołka, który jest w Q
        if( Q[ v ] && D[ v ] < Dmin ) { // i jednocześnie ma najmniejszą wartość w D
            u = v; // Znaleziony odpowiedni wierzchołek
            Dmin = D[ u ]; // i jego najmniejsza odległość od s
        }
        if( Dmin == INF ) break; // Jeżeli Dmin jest róna INF, to znaczy że Q jest puste
       
        for( v = 0; v < n; v++ ) // Przeglądamy sąsiadów wierzchołka u
        if( u != v && D[ v ] > W[ u ][ v ] + D[ u ] ) { // Czy przypadkiem droga do v przez u nie jest krótsza niż wcześniej znaleziona?
            D[ v ] = W[ u ][ v ] + D[ u ]; // Jeśli tak, to zapamiętujemy ten fakt (krótszą odległość)
            P[ v ] = u; // i przez który wierzchołek jest krócej
        }
    }
    while( 1 );
   
}

int main() { //zamieniałam void na int
    int i, j;
    cout << "Nasz graf:\n";
    for( i = 0; i < n; ++i ) {
        for( j = 0; j < n; j++ ) cout << W[ i ][ j ] << '\t';
       
        cout << endl;
    }
   
    Dijkstra( 0 );
   
    cout << "D = [";
    for( i = 0; i < n; i++ ) cout << D[ i ] << '\t' << endl;
   
    cout << "]\nP = [";
    for( i = 0; i < n; i++ ) cout << P[ i ] << '\t' << endl;
   
    cout << "]\n\n";
   
    getchar();
    return 0; //funkcja int zwraca wartośc 0
}
P-133260
pekfos
» 2015-06-06 18:01:59
P-133261
« 1 »
  Strona 1 z 1