|
</source>[[C++|<big>'''C++'''</big>]]<syntaxhighlight lang="c++" line="1">
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
const int nagative = 10000001;
int n;
vector <vector <int> > w;
vector <vector <int> > v;
void init(int N, vector <vector <int> > d) {
n = N;
w.resize(n, vector<int>(n, nagative));
v.resize(n, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
w[i][j] = d[i][j];
}
}
for (int i = 0; i < n; i++)
w[i][i] = 0;
}
void floyd() {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// i -> j 보다 k를 경유해서 가는 값이 더 작다면 경유해서 가는 가중치로 교환
if (w[i][j] > w[i][k] + w[k][j]) {
w[i][j] = w[i][k] + w[k][j];
// k -> j 가는 경로가 기록이 없다면 신규 경로 이고, 있다면 경유지의 경유지이다.
if (v[k][j] == -1) v[i][j] = k;
else v[i][j] = v[k][j];
}
}
}
}
}
void path(int i, int j) {
stack <int> s;
s.push(j);
while (v[i][s.top()] != -1) {
s.push(v[i][s.top()]);
}
s.push(i);
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << "\n";
}
</syntaxhighlight>
=== [[JAVA]] ===
<syntaxhighlight lang="java" line="1">
| 