Dijkstra算法，由荷兰计算机科学家艾兹格·迪科斯彻（Edsger W. Dijkstra）提出，是一种解决单源最短路径问题的有效算法。它适用于带非负权重的图，旨在找到从源节点到图中所有其他节点的最短路径。Dijkstra算法的核心特点是采用贪心策略，逐步扩大已知最短路径的节点集合，直至覆盖所有节点。
算法的步骤如下：
1. 初始化：设置一个源节点，其最短路径长度为0，其他所有节点的最短路径长度设为无穷大（通常用一个较大的常数表示）。创建一个集合S，初始时只包含源节点。
2. 迭代过程：在每次迭代中，从未被加入集合S的节点中选取一个具有最短路径长度的节点u，将其加入S。然后更新与u相邻的未加入S的节点的最短路径长度，如果通过u到达这些节点的路径比现有最短路径更短，则进行更新。
3. 重复步骤2，直到S包含了所有图中的节点。此时，dist数组记录了从源节点到所有其他节点的最短路径长度，而prev数组则记录了每个节点的前驱节点，即到达该节点的最短路径上的前一个节点。
C/C++实现Dijkstra算法的基本框架如下：
```cpp
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum]){
bool s[maxnum];
for(int i=1; i<=n; ++i){
dist[i] = c[v][i];
s[i] = 0;
if(dist[i] == maxint) prev[i] = 0;
else prev[i] = v;
}
dist[v] = 0;
s[v] = 1;
for(int i=2; i<=n; ++i){
int tmp = maxint;
int u = v;
for(int j=1; j<=n; ++j)
if((!s[j]) && dist[j]<tmp){
u = j;
tmp = dist[j];
}
s[u] = 1;
for(int j=1; j<=n; ++j)
if((!s[j]) && c[u][j]<maxint){
int newdist = dist[u] + c[u][j];
if(newdist < dist[j]){
dist[j] = newdist;
prev[j] = u;
}
}
}
}
```
为了打印出从源节点到目标节点的最短路径，可以使用prev数组，如下所示：
```cpp
void searchPath(int *prev, int v, int u){
int que[maxnum];
int tot = 1;
que[tot] = u;
tot++;
int tmp = prev[u];
while(tmp != v){
que[tot] = tmp;
tot++;
tmp = prev[tmp];
}
que[tot] = v;
for(int i=tot; i>=1; --i)
if(i != 1) cout << que[i] << " -> ";
else cout << que[i] << endl;
}
```
在主函数中，可以通过读取输入文件`input.txt`来填充图的邻接矩阵c，然后调用Dijkstra函数计算最短路径，最后利用searchPath函数打印路径。
Dijkstra算法虽然能够确保找到最短路径，但其效率并不高，因为它需要对所有节点进行遍历。在大型图中，可以考虑使用优先队列（如二叉堆）来提高效率，以更快地找到具有最短路径长度的节点。此外，如果图中存在负权边，Dijkstra算法将不再适用，此时可以考虑使用Bellman-Ford算法或其他适应负权重的算法。
