最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：
1.确定起点的最短路径问题：即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。
2.确定终点的最短路径问题：与确定起点的问题相反，，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
3.确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。
4.全局最短路径问题：求图中所有的最短路径。适合使用Floyd算法。
这里只给出第1种和第四种情况下两种算法的源代码。
#include "stdio.h"#define MAX 99typedef struct//图的邻接矩阵存储结构体定义{int vexs[6];int arcs[6][6];int n, e;}MGraph;void create(MGraph &G);//图的创建void Dijkstra(MGraph G, int u);//Dijkstra算法void Floyd(MGraph G);//Floyd算法int main(){MGraph G;create(G);printf("最短路径之Dijkstra算法：\n");Dijkstra(G, 0);printf("最短路径之Floyd算法：\n");Floyd(G);return 0;}void create(MGraph &G){int i, j;printf("请输入顶点数和边数：\n");scanf("%d %d", &G.n, &G.e);int b[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};for(i = 0; i < G.n; ++i)G.vexs[i] = b[i];printf("顶点编号分别为：\n");for(i = 0; i < G.n; ++i)printf("%d ", G.vexs[i]);int a[6][6]={{0, 3, MAX, MAX, MAX, MAX},{MAX, 0, 2, MAX, 6, 7},{MAX, MAX, 0, 1, 3, 4},{MAX, MAX, MAX, 0, 1, MAX},{MAX, MAX, MAX, MAX, 0, 1},{MAX, MAX, MAX, MAX, MAX, 0}};for(i = 0; i < 6; ++i)for(j = 0; j < 6; ++j)G.arcs[i][j]=a[i][j];printf("\n该图的邻接矩阵：\n");for(i = 0; i < G.n; ++i){for(j = 0; j < G.n; ++j)printf("%d ", G.arcs[i][j]);printf("\n");}}//Dijkstra算法void Dijkstra(MGraph G, int u)//假设此处从顶点0开始{int i, j, k, min;int pre[10], final[10], dist[10];for(j = 0; j < G.n; ++j){dist[j] = G.arcs[u][j];if(G.arcs[u][j] == MAX)pre[j] = -1;elsepre[j] = u;final[j] = 0;}for(i = 1; i < G.n; ++i){min = MAX;for(j = 1; j < G.n; ++j) //找出最小值的结点if( (!final[j]) && (min > dist[j])){min = dist[j];k = j;}if(min == MAX) //找不到break;final[k] = 1; //加入该结点for(j = 1; j < G.n; ++j) //更新最短路径{if((!final[j]) && (dist[j] > (dist[k] + G.arcs[k][j]))){dist[j] = dist[k] + G.arcs[k][j];pre[j] = k;}}}for(i = 1; i < G.n; ++i)//输出路径与距离{if(pre[i] == -1){printf("顶点%d到源点%d不可达。\n", i, u);continue;}printf("(%d, %d) = %d\n", i, u, dist[i]);printf("路径为:");j = i;while(j){printf("%d→", j);j = pre[j];}printf("0\n");}}//Floyd算法void Floyd(MGraph G){int i, j, k, dist[10][10], pre[10];for(i = 0; i < G.n; ++i)for(j = 0; j < G.n; ++j){dist[i][j] = G.arcs[i][j];if(dist[i][j] != MAX)pre[j] = i;elsepre[j] = -1;}for(k = 0; k < G.n; ++k)for(i = 0; i < G.n; ++i)for(j = 0; j < G.n; ++j)if((i != j) && (dist[i][j] > dist[i][k] + dist[k][j])){dist[i][j] = dist[i][k] + dist[k][j];if(dist[i][j] != MAX){pre[j] = k;pre[k] = i;}elsepre[j] = -1;}for(i = 0; i < G.n; ++i)for(j = 0; j < G.n; ++j){if(dist[i][j] == MAX)continue;else if(i != j)printf("(%d, %d) = %d\n", i, j, dist[i][j]);}printf("其余顶点之间不可达!\n");}示例：（读者可自行验证）
它不同于旅游，那需要一个风景稍微漂亮的地方，
