1. void dijkstra_lista(string nazwa_pliku, int v)
2. {
3.         int i, j, u, w, x, y, sptr, *d, *p, *S;
4.         bool *QS;                       // Zbiory Q i S
5.         slistEl **graf;                 // Tablica list sąsiedztwa
6.         slistEl *pw, *rw;
7.  
8.         ifstream dane(nazwa_pliku.c_str());
9.         dane >> m >> n >> pocz;             //  liczba krawędzi i wierzchołków
10.  
11.                                                                                 // Tworzymy tablice dynamiczne
12.  
13.         d = new int[n];                // Tablica kosztów dojścia
14.         p = new int[n];                // Tablica poprzedników
15.         QS = new bool[n];              // Zbiory Q i S
16.         graf = new slistEl *[n];       // Tablica list sąsiedztwa
17.         S = new int[n];                // Stos
18.         sptr = 0;                       // Wskaźnik stosu
19.  
20.                                                                         // Inicjujemy tablice dynamiczne
21.  
22.         for (i = 0; i < n; i++)
23.         {
24.                 d[i] = MAX_INT;
25.                 p[i] = -1;
26.                 QS[i] = false;
27.                 graf[i] = NULL;
28.         }
29.  
30.         // Odczytujemy dane wejściowe
31.  
32.         for (i = 0; i < m; i++)
33.         {
34.                 dane >> x >> y >> w;           // Odczytujemy krawędź z wagą
35.                 pw = new slistEl;             // Tworzymy element listy sąsiedztwa
36.                 pw->v = y;                    // Wierzchołek docelowy krawędzi
37.                 pw->w = w;                    // Waga krawędzi
38.                 pw->next = graf[x];
39.                 graf[x] = pw;                 // Element dołączamy do listy
40.         }
41.  
42.         cout << endl;
43.  
44.         d[v] = 0;                       // Koszt dojścia v jest zerowy
45.  
46.                                                                         // Wyznaczamy ścieżki
47.  
48.         for (i = 0; i < n; i++)
49.         {
50.                 // Szukamy wierzchołka w Q o najmniejszym koszcie d
51.  
52.                 for (j = 0; QS[j]; j++);
53.                 for (u = j++; j < n; j++)
54.                         if (!QS[j] && (d[j] < d[u])) u = j;
55.  
56.                 // Znaleziony wierzchołek przenosimy do S
57.  
58.                 QS[u] = true;
59.  
60.                 // Modyfikujemy odpowiednio wszystkich sąsiadów u, którzy są w Q
61.  
62.                 for (pw = graf[u]; pw; pw = pw->next)
63.                         if (!QS[pw->v] && (d[pw->v] > d[u] + pw->w))
64.                         {
65.                                 d[pw->v] = d[u] + pw->w;
66.                                 p[pw->v] = u;
67.                         }
68.         }
69.  
70.         // Gotowe, wyświetlamy wyniki
71.  
72.         for (i = 0; i < n; i++)
73.         {
74.                 cout << i << ": ";
75.  
76.                 // Ścieżkę przechodzimy od końca ku początkowi,
77.                 // Zapisując na stosie kolejne wierzchołki
78.  
79.                 for (j = i; j > -1; j = p[j]) S[sptr++] = j;
80.  
81.                 // Wyświetlamy ścieżkę, pobierając wierzchołki ze stosu
82.  
83.                 while (sptr) cout << S[--sptr] << " ";
84.  
85.                 // Na końcu ścieżki wypisujemy jej koszt
86.  
87.                 cout << "$" << d[i] << endl;
88.         }
89.         cout << endl;
90.  
91.         // Usuwamy tablice dynamiczne
92.  
93.         delete[] d;
94.         delete[] p;
95.         delete[] QS;
96.         delete[] S;
97.  
98.         for (i = 0; i < n; i++)
99.         {
100.                 pw = graf[i];
101.                 while (pw)
102.                 {
103.                         rw = pw;
104.                         pw = pw->next;
105.                         delete rw;
106.                 }
107.         }
108.  
109.         delete[] graf;
110.         dane.close();
111. }
112. Madzia Biernat
113. Madzia
114. struct slistEl
115. {
116.         slistEl * next;
117.         int v, w;
118. };