Graph and Appication中的一个问题，老师留的作业，解答后在这里分享解法。给出一个邻接矩阵（表明一个无向图），求取每两点之间的最短路径，邻接矩阵如下。
 
 
本题题干意为六个城市之间互有通路，城市间的飞行开销以邻接矩阵的形式给出，求取任意两城市间的最经济（开销最小）路线表。此问题可以建模为任意两点间最短路径问题，即全源最短路径问题(all-pairs shortest paths)。对此，可采用的算法有二。一是用于解决单源最短路径问题的Dijkstra算法，该算法能够求得一顶点到其他各点的最短路径，因而对所有k个顶点使用k次Dijkstra算法（后文详解）并更新到目标矩阵中即可得解；二是DP中的Floyd算法，此处不采用故不作过多介绍。以下介绍使用Dijkstra算法求解该问题（对Dijkstra算法不作详细说明，不清楚的同学可以去搜索学习一下）：
 
根据算法思想，实现该算法需要注意的两个重点在：①设置一个数组存放已被访问的结点(Node) ②设置另一个数组存放顶点到各点的距离（开始时设顶点到自身的距离为0，到其他各点的距离初始化为一个很大的值INF表示INFINITY，即不可达）
 
Dijkstra算法是能够对有向图实现全源最短路径问题的求解的，本题从给定的邻接矩阵可以看出为无向图（G[i][j] == G[j][i]），这两种情况在求解的代码上没有区别（无向图相当于两条边赋相同值）
 
我使用的编程语言为C++，工具为Sublime Text3，程序源码如下：
 
 
 
最终输出的结果同样以邻接矩阵的形式给出，如下：
 
 
 

 
 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
///本题找的是顶点1到其他各个点之间的最短路径，并将最短路径存放在dis[]这个数组里面，最后只要遍历输出这个数组就可以得到
int main()
{
 int inf=9999999;//表示无穷大，就是两个顶点之间没有链接
 int e[10][10];///表示邻接矩阵,记住一定不要把数组开的特别大，如[1000][1000],就是程序卡顿，异常闪退
 int dis[10];//表示顶点1到各个顶点之间的距离
 int book[10];//标记该定点是否是被访问
 int n,m;//顶点数和边数
 int v1,v2,length;//表示两个顶点以及之间的距离
 int min;///最小距离
 int u;///为标记的点中dis[i]值最小时对应的i,就是dis数组中元素最小的下标值
 cin>>n>>m;
 int i,j,k;
 for(i=1;i<=n;i++)///构建一个邻接矩阵
 for(j=1;j<=n;j++)
 {
 if(i==j)
 e[i][j]=0;
 else
 e[i][j]=inf;
 }
 for(i=1;i<=m;i++)///构建边，注意这里构建的是有向图，而不是无向图
 {
 cin>>v1>>v2>>length;
 e[v1][v2]=length;///有向图
 }
 for(i=1;i<=n;i++)///初始化dis数组,这里要求的是1号顶点到其余各点的初始路程
 {
 dis[i]=e[1][i];
 }
 ///初始化book数组,这里面存的是已经被标记过的点
 for (int i = 1; i <= n; i++)
 book[i] = 0;
 book[1] = 1;///表示1点是已经被标记过的点
 
 
 ///核心代码
 for(i=1;i<=n-1;i++)
 {
 min=inf;
 for(j=1;j<=n;j++)
 if(book[j]==0&&dis[j]<min)///找到dis中未标记点中的最小值,u为最小侄的下标
 {
 min=dis[j];
 u=j;
}
 book[u]=1;
 for(k=1;k<=n;k++)
 {
 if(e[u][k]<inf)
 {
 if(dis[k]>dis[u]+e[u][k])
 dis[k]=dis[u]+e[u][k];
 }
 }
 }
 for(i=1;i<=n;i++)
 cout<<dis[i]<<" ";
 return 0;
}
///输入以下
/*
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 46
*/
 
 
转载于:https://www.cnblogs.com/yang--xin/p/10661944.html

一心想学习算法，很少去真正静下心来去研究，前几天趁着周末去了解了最短路径的资料，用python写了一个最短路径算法。算法是基于带权无向图去寻找两个点之间的最短路径，数据存储用邻接矩阵记录。首先画出一幅无向图如下，标出各个节点之间的权值。
 
 
 
其中对应索引：
 
A ——> 0
 
B ——> 1
 
C ——> 2
 
D ——>3
 
E ——> 4
 
F ——> 5
 
G ——> 6
 
邻接矩阵表示无向图：
 
 
 
算法思想是通过Dijkstra算法结合自身想法实现的。大致思路是：从起始点开始，搜索周围的路径，记录每个点到起始点的权值存到已标记权值节点字典A，将起始点存入已遍历列表B，然后再遍历已标记权值节点字典A，搜索节点周围的路径，如果周围节点存在于表B，比较累加权值，新权值小于已有权值则更新权值和来源节点，否则什么都不做；如果不存在与表B，则添加节点和权值和来源节点到表A，直到搜索到终点则结束。
 
 
 
更多Python视频、源码、资料加群531509025免费获取
 
 
这时最短路径存在于表A中，得到终点的权值和来源路径，向上递推到起始点，即可得到最短路径，下面是代码：
 
 
 
运行结果：
 
 
 
学到了吗？

无向图最短路径问题
 
思路：
 具体的思路，半天也说不清楚，所以我在这里附上视屏讲解链接，里面的讲解十分清晰。
 [Djkstra算法讲解](http://www.iqiyi.com/w_19ru9nrxol.html
 
代码实现及讲解
 
#include <iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int mp[1001][1001];	//数组mp[][]，储存两点的距离
int vis[1001];	//表示某点是否参观，0 否 1 是
int dis[1001];	//存储从原点到某点的最短距离
int Max = 1e9;	//定义一个很大的数，如果两点之间的距离为该值，表示两点之间没导通
int n,m;
int main()
{
    while (scanf("%d%d",&n,&m) != EOF && m+n)
    {
        for (int i=0;i<n;i++)		//对 mp[][]初始化
            for (int j=0;j<n;j++)
            {
                if (i == j)	//同一点之间的距离为0
                    mp[i][j] = 0;
                else
                    mp[i][j] = Max;	//否则默认为两点不导通
            }

	for (int i=1;i<=m;i++)	//输入两点及之间的距离
	        {
	            int x,y,z;
	            cin>>x>>y>>z;
	            mp[x][y] = z;
	            mp[y][x] = z;
	        }
	for (int i=0;i<=n;i++)	//初始化vis[] dis[],默认为每一点都没有参观且每点到原点的距离都为无穷大
            vis[i] = 0,dis[i] = Max;
        int use;	//定义use 表示目前参观的点
        dis[1] = 0;	// 1 到 原点的距离为 0 ，也就是自己到自己

	for (int i=1;i<=n;i++)	//循环遍历 n 次，因为有n 个点，每次只能参观 1 个点
        {
            int min_num = Max;	
            //这个循环的功能就是找到为参观的节点中dis[]最小的那个点
            //这里注意，是先知道dis[j]到原点的距离，才能判断 j 点是否参观 
            for (int j=1;j<=n;j++)
            {
                if (vis[j] == 0 && dis[j] < min_num)
                {
                    use = j;
                    min_num = dis[j];
                }
            }
            vis[use] = 1;	//查找到，则参观该点
            for (int j=1;j<=n;j++)	//遍历所以未参观的点且未参观的点与该参观点导通，求出未参观点与参观点导通的点间最小值，则求出 j 点到原点的距离。
                if (mp[use][j] && vis[j] == 0 && dis[j] > dis[use] + mp[use][j])
                    dis[j] = dis[use] + mp[use][j];
        }
        for (int i=1;i<=n;i++)
        printf("%d\t",dis[i]);
    }
    return 0;
}