鏈接:
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1219
這個題就是求出所有結點的距離之后,再找出某個結點,該結點離其它結點的最大距離是所有結點中是最小的...
解法1:深搜出所有結點間的距離,但是會超時,即使深搜的過程使用中記憶化搜索(就是用2維數組保存已經搜出的答案,如果后面的搜索需要用到直接使用即可)...
解法2:Floyd算法,3重循環直接找出所有結點之間的最短距離
解法3:對每一個結點應用一次迪杰斯特拉算法,找出所有結點與其它結點間的最短距離...
解法2:
#include <stdio.h>
#include <string.h>
#define MAX (100 + 10)
#define INF (1000000 + 10)
int nN, nM;
int nDis[MAX][MAX];
void SearchAll()
{
for (int k = 0; k < nN; ++k)
{
for (int i = 0; i < nN; ++i)
{
for (int j = 0; j < nN; ++j)
{
if (nDis[i][k] + nDis[k][j] < nDis[i][j])
{
nDis[i][j] = nDis[j][i] = nDis[i][k] + nDis[k][j];
}
}
}
}
}
int main()
{
while (scanf("%d%d", &nN, &nM) == 2)
{
for (int i = 0; i < nN; ++i)
{
for (int j = 0; j < nN; ++j)
{
if (i == j)
{
nDis[i][j] = 0;
}
else
{
nDis[i][j] = INF;
}
}
}
while (nM--)
{
int nX, nY, nK;
scanf("%d%d%d", &nX, &nY, &nK);
nDis[nX][nY] = nDis[nY][nX] = nK;
}
SearchAll();
bool bOk = false;
int nMin = 1 << 30;
for (int i = 0; i < nN; ++i)
{
int nTemp = 0;
int j = 0;
for ( ; j < nN; ++j)
{
if (i == j) continue;
if (nDis[i][j] == INF)
{
break;
}
else
{
if (nDis[i][j] > nTemp)
{
nTemp = nDis[i][j];
}
}
}
if (j == nN)
{
bOk = true;
if (nTemp < nMin)
{
nMin = nTemp;
}
}
}
if (bOk)
{
printf("%d\n", nMin);
}
else
{
printf("Can not\n");
}
}
return 0;
}
關于Floyd算法,可以這樣理解...比如剛開始只取2個結點i,j,它們的距離一定是dis(i,j),但是還有其它結點,需要把其它結點也慢慢加進來,所以最外層關于k的循環意思就是從0至nN-1,把所有其它結點加進來,比如加入0號結點后,距離dis(i,0)+dis(0,j)可能會比dis(i,j)小,如果是這樣就更新dis(i,j),然后后面加入1號結點的時候,實際上是在已經加入0號結點的基礎上進行的處理了,效果變成dis(i,0,1,j),可能是最小的,而且中間的0,1也可能是不存在的,當然是在dis(i,j)原本就是最小的情況下...
這個算法可以用下面這個圖片描述...
解法3:
#include <stdio.h>
#include <string.h>
#define MAX (100 + 10)
#define INF (1000000 + 10)
int nN, nM;
int nDis[MAX][MAX];
void Search(int nSource)
{
bool bVisit[MAX];
memset(bVisit, false, sizeof(bVisit));
bVisit[nSource] = true;
for (int i = 0; i < nN - 1; ++i)
{
int nMin = INF;
int nMinPos = 0;
for (int j = 0; j < nN; ++j)
{
if (!bVisit[j] && nDis[nSource][j] < nMin)
{
nMin = nDis[nSource][j];
nMinPos = j;
}
}
if (bVisit[nMinPos] == false)
{
bVisit[nMinPos] = true;
for (int j = 0; j < nN; ++j)
{
if (nDis[nSource][nMinPos] + nDis[nMinPos][j] < nDis[nSource][j])
{
nDis[nSource][j] = nDis[nSource][nMinPos] + nDis[nMinPos][j];
}
}
}
}
}
void SearchAll()
{
for (int k = 0; k < nN; ++k)
{
Search(k);
}
}
int main()
{
while (scanf("%d%d", &nN, &nM) == 2)
{
for (int i = 0; i < nN; ++i)
{
for (int j = 0; j < nN; ++j)
{
if (i == j)
{
nDis[i][j] = 0;
}
else
{
nDis[i][j] = INF;
}
}
}
while (nM--)
{
int nX, nY, nK;
scanf("%d%d%d", &nX, &nY, &nK);
nDis[nX][nY] = nDis[nY][nX] = nK;
}
SearchAll();
bool bOk = false;
int nMin = 1 << 30;
for (int i = 0; i < nN; ++i)
{
int nTemp = 0;
int j = 0;
for ( ; j < nN; ++j)
{
if (i == j) continue;
if (nDis[i][j] == INF)
{
break;
}
else
{
if (nDis[i][j] > nTemp)
{
nTemp = nDis[i][j];
}
}
}
if (j == nN)
{
bOk = true;
if (nTemp < nMin)
{
nMin = nTemp;
}
}
}
if (bOk)
{
printf("%d\n", nMin);
}
else
{
printf("Can not\n");
}
}
return 0;
}
迪杰斯特拉算法的核心思想是維護一個源點頂點集合,任何最短路徑一定是從這個頂點集合發出的...
初始化時,這個集合就是源點...
我們從該其它結點中選出一個結點,該結點到源點的距離最小...
顯然,這個距離就是源點到該結點的最短距離了,我們已經找到了答案的一部分了...然后,我們就把該結點加入前面所說的頂點集合...
現在頂點集合更新了,我們必須得更新距離了...由于新加入的結點可能發出邊使得原來源點到某些結點的距離更小,也就是我們的源點變大了,邊也變多了,所以我們的最短距離集合的值也必須變化了...
該算法一直循環nN-1次,直至所有的點都加入源點頂點集合...