【问题描述】最短路径问题实际上是带权有向图（网）的一种应用，用Dijkstra算法求两个顶点间的最短路径。备注：输入的有向网信息中0表示不存在顶点到自身的弧，32767表示两个顶点之间不存在弧。 【输入形式】带权有向图（网）的顶点数及，有向图（网）的信息，出发顶点。 【输出形式】输出出发顶点到有向图（网）其余顶点间的最短路径长度及其路径。 【样例输入】 输入顶点数： 7 输入有向网的信息： 0 4 6 6 32767 32767 32767 32767 0 1 32767 7 32767 32767 32767 32767 0 32767 6 4 32767 32767 32767 2 0 32767 5 32767 32767 32767 32767 32767 0 32767 6 32767 32767 32767 32767 1 0 8 32767 32767 32767 32767 32767 32767 0 输入出发顶点： 0 【样例输出】 从0顶点出发的最短路径如下: 从顶点0到顶点1的路径长度为:4 路径为:0,1 从顶点0到顶点2的路径长度为:5 路径为:0,1,2 从顶点0到顶点3的路径长度为:6 路径为:0,3 从顶点0到顶点4的路径长度为:10 路径为:0,1,2,5,4 从顶点0到顶点5的路径长度为:9 路径为:0,1,2,5 从顶点0到顶点6的路径长度为:16 路径为:0,1,2,5,4,6 使用c++解决该问题

以下是使用C++语言实现Dijkstra算法求解带权有向图最短路径的代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 32767; // 定义无穷大
const int MAXN = 100; // 定义最大顶点数

int n; // 顶点数
int G[MAXN][MAXN]; // 有向图的邻接矩阵表示
int d[MAXN]; // 存储起点到各个顶点的最短距离
bool visited[MAXN]; // 标记每个顶点是否已被访问

// Dijkstra算法求解最短路径
void Dijkstra(int s)
{
    fill(d, d + n, INF); // 初始化起点到各个顶点的距离为无穷大
    fill(visited, visited + n, false); // 初始化所有顶点为未访问状态
    d[s] = 0; // 起点到自身的距离为0
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; // 小根堆，存储距离和顶点编号
    pq.push(make_pair(0, s)); // 将起点加入堆中
    while (!pq.empty())
    {
        // 取出堆顶元素
        pair<int, int> p = pq.top();
        pq.pop();
        int v = p.second; // 取出顶点编号
        if (visited[v]) continue; // 如果该顶点已被访问，直接跳过
        visited[v] = true; // 标记该顶点为已访问
        // 更新与该顶点相邻的顶点到起点的距离
        for (int i = 0; i < n; i++)
        {
            if (!visited[i] && G[v][i] < INF)
            {
                if (d[i] > d[v] + G[v][i])
                {
                    d[i] = d[v] + G[v][i];
                    pq.push(make_pair(d[i], i)); // 将更新后的顶点加入堆中
                }
            }
        }
    }
}

int main()
{
    // 输入有向图信息
    cout << "输入顶点数：";
    cin >> n;
    cout << "输入有向网的信息：" << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> G[i][j];
        }
    }
    // 输入出发顶点
    int s;
    cout << "输入出发顶点：";
    cin >> s;
    // 求解最短路径
    Dijkstra(s);
    // 输出最短路径长度及其路径
    cout << "从" << s << "顶点出发的最短路径如下：" << endl;
    for (int i = 0; i < n; i++)
    {
        if (d[i] < INF)
        {
            cout << "从顶点" << s << "到顶点" << i << "的路径长度为：" << d[i] << " 路径为：" << s;
            int j = i;
            while (j != s)
            {
                for (int k = 0; k < n; k++)
                {
                    if (G[k][j] < INF && d[k] + G[k][j] == d[j])
                    {
                        cout << "," << k;
                        j = k;
                        break;
                    }
                }
            }
            cout << endl;
        }
        else
        {
            cout << "从顶点" << s << "到顶点" << i << "不存在路径" << endl;
        }
    }
    return 0;
}

在输入带权有向图的信息和出发顶点后，该程序会输出出发顶点到有向图其他顶点的最短路径长度及其路径。