グラフ理論における最短経路問題は、ダイクストラ法（Dijkstra's Algorithm）を用いることで、負の重みを持たないグラフにおいて効率的に解くことができます。以下に、隣接リスト形式でグラフを表現し、指定された始点から終点までの最短経路を算出する実装例を示します。

実装例

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Edge {
    int to;
    int weight;
};

const int INF = INT_MAX;

void reconstruct_path(const vector<int>& parent, const vector<int>& nodes, int target) {
    if (target == -1) return;
    if (parent[target] != -1) {
        reconstruct_path(parent, nodes, parent[target]);
        cout << "-->";
    }
    cout << nodes[target];
}

int main() {
    int num_nodes, num_edges;
    cin >> num_nodes >> num_edges;

    vector<int> node_labels(num_nodes);
    for (int i = 0; i < num_nodes; ++i) cin >> node_labels[i];

    auto get_index = [&](int val) {
        for (int i = 0; i < num_nodes; ++i) 
            if (node_labels[i] == val) return i;
        return -1;
    };

    vector<vector<Edge>> adj(num_nodes);
    for (int i = 0; i < num_edges; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[get_index(u)].push_back({get_index(v), w});
    }

    int start_node, end_node;
    cin >> start_node >> end_node;
    int s = get_index(start_node), t = get_index(end_node);

    vector<int> dist(num_nodes, INF);
    vector<int> parent(num_nodes, -1);
    vector<bool> visited(num_nodes, false);

    dist[s] = 0;

    for (int i = 0; i < num_nodes; ++i) {
        int u = -1;
        for (int j = 0; j < num_nodes; ++j) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) u = j;
        }

        if (dist[u] == INF) break;
        visited[u] = true;

        for (auto& edge : adj[u]) {
            if (dist[edge.to] > dist[u] + edge.weight) {
                dist[edge.to] = dist[u] + edge.weight;
                parent[edge.to] = u;
            }
        }
    }

    reconstruct_path(parent, node_labels, t);

    return 0;
}

このコードでは、std::vectorを使用して隣接リストを管理し、dist配列で始点からの最小コストを、parent配列で経路を追跡するための直前の頂点を記録します。ダイクストラ法は未確定の頂点のうち最短距離を持つものを貪欲に選択し、その頂点を経由して各隣接頂点の距離を更新することで、最終的な最短経路を導き出します。