dast
Anmeldungsdatum: 28.06.2005
Beiträge: 2
Wohnort: Österreich - Tirol
|
 Verfasst am: 28. Jun 2005 23:28 Titel: |
 |
|
Falls noch relevant für dich, hier mal mein C-Code zum Dijkstra-Algorithmus:
| Code: | // dijkstra.cpp
#include <iostream>
#include <iomanip>
#include <limits>
using namespace std;
// A ... Bregenz
// B ... Landeck
// C ... Sölden
// D ... Innsbruck
// E ... Kufstein
// F ... Lienz
// G ... Zell am See
// H ... Salzburg
// I ... Passau
// J ... Villach
// K ... Wels
// L ... Klagenfurt
// M ... Linz
// N ... Judenburg
// O ... Graz
// P ... Krems
// Q ... St. Pölten
// R ... ?
// S ... Wien
// T ... Eisenstadt
const int n = 20;
const int A[n][n] = { // A B C D E F G H I J K L M N O P Q R S T
/* A */ { 0, 115, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
/* B */ { 115, 0, 64, 73, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
/* C */ { -1, 64, 0, 84, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
/* D */ { -1, 73, 84, 0, 75, 176, 140, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
/* E */ { -1, -1, -1, 75, 0, -1, 77, 93, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
/* F */ { -1, -1, -1, 176, -1, 0, 90, -1, -1, 107, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
/* G */ { -1, -1, -1, 140, 77, 90, 0, 79, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
/* H */ { -1, -1, -1, -1, 93, -1, 79, 0, -1, 180, 96, -1, -1, 191, -1, -1, -1, -1, -1, -1 },
/* I */ { -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, 75, -1, 77, -1, -1, -1, -1, -1, -1, -1 },
/* J */ { -1, -1, -1, -1, -1, 107, -1, 180, -1, 0, -1, 40, -1, -1, -1, -1, -1, -1, -1, -1 },
/* K */ { -1, -1, -1, -1, -1, -1, -1, 96, 75, -1, 0, -1, 29, 147, -1, -1, -1, -1, -1, -1 },
/* L */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, 40, -1, 0, -1, 94, -1, -1, -1, -1, -1, -1 },
/* M */ { -1, -1, -1, -1, -1, -1, -1, -1, 77, -1, 29, -1, 0, -1, -1, -1, 120, -1, -1, -1 },
/* N */ { -1, -1, -1, -1, -1, -1, -1, 191, -1, -1, 147, 94, -1, 0, 81, -1, -1, 141, -1, -1 },
/* O */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 81, 0, -1, -1, 117, -1, -1 },
/* P */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 27, -1, 76, -1 },
/* Q */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 120, -1, -1, 27, 0, -1, 65, -1 },
/* R */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 141, 117, -1, -1, 0, 68, 39 },
/* S */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 76, 65, 68, 0, 55 },
/* T */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 39, 55, 0 } };
void init(bool U[], int S[], int D[], int P[], int start)
{
for (int i = 0; i < n; i++)
{
D[i] = -1;
S[i] = P[i] = 0;
U[i] = true;
}
D[start - 1] = 0;
}
int getNodeWithMinD(const bool U[], const int D[])
{
int d = numeric_limits<int>::max();
int j = -1;
for (int i = 0; i < n; i++)
{
if (U[i] && D[i] != -1 && D[i] < d)
{
j = i;
d = D[i];
}
}
return j;
}
void relax(const bool U[], int D[], int P[], int v)
{
for (int w = 0; w < n; w++)
{
if (U[w] && A[v][w] != -1)
{
if (D[w] == -1 || D[v] + A[v][w] < D[w])
{
D[w] = D[v] + A[v][w];
P[w] = v + 1;
}
}
}
}
void plot(const int S[], const int D[], const int P[])
{
cout << "{ ";
int j = 0;
for (; j < n && S[j] > 0; j++)
{
cout << char('A'+S[j]-1);
if (j < n - 1 && S[j+1] > 0)
cout << ", ";
}
cout << " } ";
for (; j < n; j++)
{
cout << " ";
}
for (j = 0; j < n; j++)
{
cout << " " << setfill(' ') << setw(3) << D[j] << " ";
if (P[j] > 0)
cout << char('A'+P[j]-1);
else
cout << 0;
}
cout << endl;
}
void plotD(const int D[])
{
cout << "D = [ ";
for (int i = 0; i < n; i++)
{
if (D[i] != -1)
cout << D[i];
else
cout << 0;
if (i < n - 1)
cout << ", ";
}
cout << " ]" << endl;
}
void plotP(const int P[])
{
cout << "P = [ ";
for (int i = 0; i < n; i++)
{
if (P[i] > 0)
cout << char('A'+P[i]-1);
else
cout << 0;
if (i < n - 1)
cout << ", ";
}
cout << " ]" << endl;
}
void plotWay(const int P[], int start, int end)
{
int j = end, cost = 0;
cout << char('A'+start-1) << " -> " << char('A'+end-1) << ": " << endl;
while (j != start)
{
cout << "P[" << char('A'+j-1) << "] = ";
cost += A[P[j-1]-1][j-1];
j = P[j-1];
cout << char('A'+j-1) << endl;
}
cout << "cost = " << cost << endl;
}
bool getArgs(int argc, char* argv[], int& start, int& end)
{
if (argc < 3)
{
cout << "Usage: dijkstra <start> <end>" << endl;
return false;
}
if (strlen(argv[1]) > 1 || strlen(argv[2]) > 1)
{
cout << "Invalid argument." << endl;
return false;
}
start = toupper(argv[1][0]) - 'A' + 1;
end = toupper(argv[2][0]) - 'A' + 1;
if (start < 1 || start > n || end < 1 || end > n)
{
cout << "Invalid argument." << endl;
return false;
}
return true;
}
int main(int argc, char* argv[])
{
int start, end;
if (!getArgs(argc, argv, start, end))
return -1;
bool U[n];
int S[n], D[n], P[n];
init(U, S, D, P, start);
for (int i = 0; i < n; i++)
{
int v = (i > 0) ? getNodeWithMinD(U, D) : start - 1;
U[v] = false;
S[i] = v + 1;
relax(U, D, P, v);
plot(S, D, P);
}
cout << endl;
plotD(D);
plotP(P);
cout << endl;
plotWay(P, start, end);
return 0;
}
|
MFG Daniel.
_________________
FIND A JOB YOU LOVE, AND YOU'LL NEVER HAVE TO WORK A DAY OF YOUR LIFE.  |
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
