邻接矩阵储存无向图的广度优先遍历，模拟队列求最小转机次数。

#include <iostream>
using namespace std;
typedef struct queue
{
    int x;//当前城市编号
    int s;//转机次数
}Queue;

int e[60][60] = {0}, book[60] = {0};

int main()
{
    Queue que[2510];

    int n, m, start, end, flag = 0;
    cin >> n >> m >> start >> end;

    //无向图初始化
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
                e[i][j] = 0;
            else 
                e[i][j] = 99999999;
        }
    }

    //读入转机信息
    int a, b;
    for(int i = 1; i <= m; i++)
    {
        cin >> a >> b;
        e[a][b] = 1;
        e[b][a] = 1;
    }

    //队列初始化    
    int head, tail;
    head = 1;
    tail = 1;
    que[tail].x = start;
    que[tail].s = 0;
    tail++;
    book[start] = 1;

    int cur;
    while(head < tail)
    {
        cur = que[head].x;
        for(int i = 1; i <= n; i++)
        {
            if(e[cur][i] != 99999999 && book[i] == 0)
            {
                book[i] = 1;
                que[tail].x = i;
                que[tail].s = que[head].s + 1;
                tail++;
            }

            if(que[tail - 1].x == end)
            {
                flag = 1;
                break;
            }
        }
        if(flag == 1)
            break;
        head++;
    }

    cout << que[tail - 1].s << endl;

    return 0;
}

测试输入：

5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

输出结果：

2