📄 算法.htm
字号:
path<i>[j] = i;<br />
for (k = 0; k < n; k++) <br />
for (i = 0; i < n; i++) <br />
for (j = 0; j < n; j++) <br />
if (dist<i>[j] > MAXSUM(dist<i>[k], dist[k][j])) <br />
{<br />
path<i>[j] = path[k][j]; <br />
dist<i>[j] = MAXSUM(dist<i>[k], dist[k][j]);<br />
}<br />
}<br />
<br />
void display_path(int dist[][MAXSIZE], int path[][MAXSIZE], int n)<br />
{<br />
int *chain;<br />
int count;<br />
int i, j, k;<br />
printf("\n\nOrigin->Dest Dist Path");<br />
printf( "\n-----------------------------");<br />
chain = (int *) malloc(sizeof(int)*n);<br />
for (i = 0; i < n; i++) <br />
for (j = 0; j < n; j++)<br />
{<br />
if (i != j)<br />
{ <br />
printf("\n%6d->%d ", i+1, j+1);<br />
if (dist<i>[j] == INT_MAX) <br />
printf(" NA "); <br />
else<br />
{<br />
printf("%4d ", dist<i>[j]);<br />
count = 0; <br />
k = j;<br />
do<br />
{<br />
k = chain[count++] = path<i>[k];<br />
} while (i != k);<br />
reverse(chain, count); <br />
printf("%d", chain[0]+1); <br />
for (k = 1; k < count; k++)<br />
printf("->%d", chain[k]+1);<br />
printf("->%d", j+1);<br />
}<br />
}<br />
}<br />
free(chain); <br />
}<br />
<br />
#define SWAP(a, b) { temp = a; a = b; b = temp; }<br />
<br />
void reverse(int x[], int n)<br />
{<br />
int i, j, temp;<br />
for (i = 0, j = n-1; i < j; i++, j--)<br />
SWAP(x<i>, x[j]);<br />
}<br />
<br />
void readin(int dist[][MAXSIZE], int *number)<br />
{<br />
int origin, dest, length, n;<br />
int i, j;<br />
char line[100];<br />
gets(line); <br />
sscanf(line, "%d", &n);<br />
*number = n;<br />
for (i = 0; i < n; i++) <br />
{<br />
for (j = 0; j < n; j++)<br />
dist<i>[j] = INT_MAX;<br />
dist<i><i> = 0; <br />
}<br />
gets(line); <br />
sscanf(line, "%d%d%d", &origin, &dest, &length);<br />
while (origin != 0 && dest != 0 && length != 0)<br />
{<br />
dist[origin-1][dest-1] = length;<br />
gets(line); <br />
sscanf(line, "%d%d%d", &origin, &dest, &length);<br />
}<br />
}<br />
测试程序如下所示：<br />
int main(void)<br />
{<br />
int dist[MAXSIZE][MAXSIZE];<br />
int path[MAXSIZE][MAXSIZE];<br />
int n;<br />
printf("\nInput the path information:");<br />
printf("\n----------------------------\n");<br />
readin(dist, &n);<br />
floyd(dist, path, n);<br />
display_path(dist, path, n);<br />
getchar();<br />
}<br />
其中readin函数规定了输入的格式，第一列是指出有多少个城市；第二列以后每行三个数；第一个和第二个是一条路径的起点和终点，第三个数是路径的长度，最后以三个0作为输入结束条件。下面是一个输入的例子：<br />
Input the path information:<br />
--------------------------------------<br />
4<br />
1 2 5<br />
2 1 50<br />
2 3 15<br />
2 4 5<br />
3 1 30<br />
3 4 15<br />
4 1 15<br />
4 3 5<br />
0 0 0<br />
对应的输出结果为：<br />
Origin->Dest Dist Path<br />
----------------------------------------------<br />
1->2 5 1->2<br />
1->3 15 1->2->4->3<br />
1->4 10 1->2->4<br />
2->1 20 2->4->1<br />
2->3 10 2->4->3<br />
2->4 5 2->4<br />
3->1 30 3->1<br />
3->2 35 3->1->2<br />
3->4 15 3->4<br />
4->1 15 4->1<br />
4->2 20 4->1->2<br />
4->3 5 4->3</i></i></i></i></i></i></i></i></i></i></i></i></i></span></div>
<fieldset>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -