用邻接矩阵a表示一幅图,a[i][j]表示从点i到点j的边长,如果为0则无边.(这是无负边,0边的情况)
这张图有T个点,C条边,要求求出从Ts走到Te的最短路.
用f[i]表示从Ts走到i点的最短路(这是动态规划思想),那么最后的答案就是f[Te].
与广搜类似,用一个数组q来表示队列,h是队头指针,t是队尾指针,直到h>=t就扫完了,停止入队,用布尔数组b表示点是否在队列内.
伪代码:
while (没扫完) { 队头出队; b[新的对头]=false;//因为只要有更短的路径就可以重复入队 for (扫一遍所有点) if (q[h]到i间有边 且 q[h]到i的边加上Ts到q[h]的边比Ts到i的路要短) { Ts到i的最短路为q[h]到i的边加上Ts到q[h]的边; if (i不在队内) i入队; } }
注意:只要有更短的路径就可以重复入队,因此q就要开得大一点.
好吧,我现在还没有AC一道题,只得了70分,代码放上来请大家帮我看看.我用C++STL里面的队列再做一下.
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <climits> using namespace std; int T, C, Ts, Te, a[2500][2500], f[2500], q[5000], h = 0, t = 1; bool b[2500]; int main() { memset(a, -1, sizeof(a)); memset(b, 0, sizeof(b)); scanf("%d%d%d%d", &T, &C, &Ts, &Te); for (int i = 1; i <= T; i++) f[i] = INT_MAX / 3; for (int i = 1, Rs, Re, ci; i <= C; i++) { scanf("%d%d%d", &Rs, &Re, &ci); a[Rs][Re] = a[Re][Rs] = ci; } f[Ts] = 0; q[1] = Ts; b[1] = true; while (h <= t) { h++; b[h] = false; for (int i = 1; i <= T; i++) if ((a[q[h]][i] > 0) && (a[q[h]][i] + f[q[h]] < f[i])) { f[i] = a[q[h]][i] + f[q[h]]; if (!b[i]) { t++; b[i] = true; q[t] = i; } } } cout << f[Te]; return 0; }