| Dijkstra
数组实现
O
（
N^2
）
| Dijkstra ---
数组实现
(
在此基础上可直接改为
STL
的
Queue
实现
)
| lowcost[] --- beg
到其他点的最近距离
| path[] -- beg
为根展开的树，记录父亲结点
\*==================================================*/
#define INF 0x03F3F3F3F
const int N;
int path[N], vis[N];
void Dijkstra(int cost[][N], int lowcost[N], int n, int beg){
int i, j, min;
memset(vis, 0, sizeof(vis));
vis[beg] = 1;
for (i=0; i
lowcost[i] = cost[beg][i]; path[i] = beg;
}
lowcost[beg] = 0;
path[beg] = -1; //
树根的标记
int pre = beg;
for (i=1; i
min = INF;
for (j=0; j
//
下面的加法可能导致溢出
,INF
不能取太大
if (vis[j]==0 &&
lowcost[pre]+cost[pre][j]
lowcost[j] = lowcost[pre] + cost[pre][j];
path[j] = pre;
}
for (j=0; j
if (vis[j] == 0 && lowcost[j] < min){
min = lowcost[j]; pre = j;
}
vis[pre] = 1;
}
}