Posted on 2009-04-09 23:02
lzmagic 閱讀(1894)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm
/**//**
* CRITICALPATH(簡單版) 關鍵路徑
* 輸入：無環圖g。
* 輸出：(1)各點最早完成時間ec；
* (2)各點最晚完成時間lc；
* (3)關鍵路徑prev。
* 結構：圖g用鄰接矩陣表示
* 算法：拓撲排序，動態規劃(DP)
* 復雜度：O(|V|^2)
*/
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;
int n; // n ：頂點個數
vector<vector<int> > g; // g ：圖(graph)(用鄰接矩陣(adjacent matrix)表示)
vector<int> seq; // seq ：拓撲序列(sequence)
bool TopSort() // 拓撲排序
{
vector<int> inc(n, 0);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (g[i][j] < INT_MAX) ++inc[j]; // 計算每個頂點的入度，
queue<int> que;
for (int j = 0; j < n; ++j)
if (inc[j] == 0) que.push(j); // 如果頂點的入度為0，入隊。
int seqc = 0;
seq.resize(n);
while (!que.empty()) // 如果隊列que非空，
{
int v = que.front(); que.pop();
seq[seqc++] = v; // 頂點v出隊，放入seq中，
for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點w，
if (g[v][w] < INT_MAX)
if (--inc[w] == 0) que.push(w); // 調整w的入度，如果w的入度為0，入隊。
}
return seqc == n; // 如果seq已處理頂點數為n，存在拓撲排序，否則存在回路。
}
vector<int> ec; // ec : 最早完成時間(early complete time)
vector<int> lc; // lc : 最晚完成時間(late complete time)
vector<int> cp; // cp : 關鍵路徑(critical path)
void CriticalPath() // 關鍵路徑
{
// 最早完成時間：ec[0] = 0;
// ec[v] = max(ec[u] + g[u][v])。
ec.assign(n, INT_MIN); ec[seq[0]] = 0;
for (int i = 0; i < n - 1; ++i)
for (int v = 0; v < n; ++v)
if (g[seq[i]][v] < INT_MAX)
ec[v] = max(ec[v], ec[seq[i]] + g[seq[i]][v]);
// 最晚完成時間：lc[n - 1] = ec[n - 1];
// lc[u] = min(lc[v] - g[u][v])。
lc.assign(n, INT_MAX); lc[seq[n - 1]] = ec[seq[n - 1]];
for (int j = n - 1; j > 0; --j)
for (int u = 0; u < n; ++u)
if (g[u][seq[j]] < INT_MAX)
lc[u] = min(lc[u], lc[seq[j]] - g[u][seq[j]]);
// 關鍵路徑：cp[0] = seq[0];
// if(松弛時間slack(u, v) = lc[v] - ec[u] - g[u][v]為零)
// { u為關鍵路徑點；如果u為seq[n - 1]，結束。}
cp.clear(); cp.push_back(seq[0]);
for (int i = 0; i < n - 1; ++i)
{
for (int v = 0; v < n; ++v)
if (g[cp[i]][v] < INT_MAX)
{
int slack = lc[v] - ec[cp[i]] - g[cp[i]][v];
if (slack == 0) { cp.push_back(v); break; }
}
if (cp.back() == seq[n - 1]) break;
}
}
int main()
{
n = 9;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = 6; g[0][2] = 4; g[0][3] = 5;
g[1][4] = 1;
g[2][4] = 1;
g[3][5] = 2;
g[4][6] = 9; g[4][7] = 7;
g[5][7] = 4;
g[6][8] = 2;
g[7][8] = 4;
if (TopSort())
{
copy(seq.begin(), seq.end(), ostream_iterator<int>(cout, " ")); cout << endl;
CriticalPath();
copy(ec.begin(), ec.end(), ostream_iterator<int>(cout, " ")); cout << endl;
copy(lc.begin(), lc.end(), ostream_iterator<int>(cout, " ")); cout << endl;
copy(cp.begin(), cp.end(), ostream_iterator<int>(cout, " ")); cout << endl;
}
else
{
cout << "Circles exist." << endl;
}
system("pause");
return 0;
}