top--;
if (top >= 0) //转向下一条边
{
Vex[top]++;
}
}
}
printf("搜索次数为 %d\n", sum);
return Dis[endPos];
}
int Dijkstra(int n, int startPos, int endPos)//Dijkstra最短路径算法
{
int i, j, v, min;
int Dis[MAX] = {0};
int sum = 0;
for (i=0; i
for (i=0; i
book[startPos] = 1;
for (j=1; j
min = MAXLEN; //城市间最短距离
v = startPos;
for (i=0; i
if (book[i] == 0 && Dis[i] < min)
{
min = Dis[i];
v = i;
}
sum++;
}
if (v == endPos) //已经找到最短路径
break;
book[v] = 1;
for (i=0; i
if (map[v][i] != MAXLEN)
{
if (Dis[i] > Dis[v] + map[v][i])
Dis[i] = Dis[v] + map[v][i];
}
sum++;
}
}
printf("搜索次数为 %d\n", sum);
return Dis[endPos];
}
int bfs(int n, int startPos, int endPos)//改进的广度优先搜索最短路径算法
{
int i, k, front, rear;
int Dis[MAX] = {0};
int Queue[MAX] = {0};
int sum = 0;
for (i=0; i
for (i=0; i
Dis[startPos] = 0;
book[startPos] = 1;
front = rear = 0;
Queue[rear++] = startPos;
while (front != rear)
{
k = Queue[front];
for (i=0; i
if (Dis[i] > Dis[k] + map[k][i])
{
Dis[i] = Dis[k] + map[k][i];
if (book[i] == 0)//入队列
{
Queue[rear] = i;
rear = (rear + 1) % MAX;
book[i] = 1;
}
}
sum++;
}
book[k] = 0;
front = (front + 1) % MAX;
}
printf("搜索次数为 %d\n", sum);
return Dis[endPos];
}
int Floyd(int n, int startPos, int endPos)//Floyd-Warshall最短路径算法
{
int i, j, flag;
int Dis[MAX] = {0};
int sum = 0;
for (i=0; i
flag = 1;
while (flag)
{
flag = 0;
for (i=0; i
for (j=0; j
if (Dis[i] > Dis[j] + map[j][i])
{
Dis[i] = Dis[j] + map[j][i];
flag = 1;
}
sum++;
}
}
}
printf("搜索次数为 %d\n", sum);
return Dis[endPos];
}
int Floyd2(int n, int startPos, int endPos)//Floyd-Warshall最短路径算法（原始版）
{
int i, j, k;
int Dis[MAX][MAX] = {0};
int sum = 0;
for (i=0; i
for (k=0; k
for (i=0; i
for (j=0; j
if (Dis[i][j] > Dis[i][k] + Dis[k][j])
{
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
sum++;
}
}
}
printf("搜索次数为 %d\n", sum);
return Dis[startPos][endPos];
}
int Bellman(int n, int startPos, int endPos)//Bellman-Fort最短路径算法
{
int i, j, m = 0;
int Dis[MAX] = {0};
int u[MAX*MAX] = {0};
int v[MAX*MAX] = {0};
int w[MAX*MAX] = {0};
int sum = 0;
for (i=0; i
for (j=0; j
if (i != j && map[i][j] != MAXLEN)
{
u[m] = i;
v[m] = j;
w[m++] = map[i][j];
}
}
}
for (i=0; i
for (i=1; i
for (j=0; j
if (Dis[v[j]] > Dis[u[j]] + w[j])
{
Dis[v[j]] = Dis[u[j]] + w[j];
}
sum++;
}
}
printf("搜索次数为 %d\n", sum);
return Dis[endPos];
}