Description
Finding the shortest path is a classic problem discussed in the Graph data structure.
Given a graph below, please find the shortest path between a specified pair of vertices and print out the path.
For example, the distance of the shortest path from vertex 0 to vertex 8 is 16
and the path is 0→1→2→4→3→6→7→8.
A partial sample code is listed below for your reference, but you may apply any preferred shortest path algorithm and ignore the reference code.
(you may use any of the Dijkstra, Bellmanford, Floyd-Warshall, ..., algorithms! But do not try to calculate the shortest path by hand and just fill in the value in your code. You should implement an algorithm to solve the problem!)
#include<iostream>
#include<vector>
using namespace std;
class MatrixGraph{
private:
int Graph[MAXVEX][MAXVEX];
int start,destination;
// You can define any member by yourself
public:
MatrixGraph();
MatrixGraph(int start,int destination);
void ShortestPath(const int v);
void getPath(const int d);
};
MatrixGraph::MatrixGraph(int start,int destination){
this->start=start;
this->destination=destination;
for(int i=0;i<MAXVEX;i++){
for(int j=0;j<MAXVEX;j++){
Graph[i][j]=INFINITY;
}
Graph[i][i]=0;
}
Graph[1][0]=1; Graph[2][0]=5; Graph[2][1]=3; Graph[3][1]=7;
Graph[4][1]=5; Graph[4][2]=1; Graph[4][3]=2; Graph[5][2]=7;
Graph[5][4]=3; Graph[6][3]=3; Graph[6][4]=6; Graph[7][4]=9;
Graph[7][5]=5; Graph[7][6]=2; Graph[8][6]=7; Graph[8][7]=4;
for(int i=0;i<MAXVEX;i++){
for(int j=0;j<MAXVEX;j++){
if( i>j && Graph[i][j]!=INFINITY ){
Graph[j][i]=Graph[i][j];
}
}
}
}
void MatrixGraph::ShortestPath(const int v){
// We start from vertex v to find the shortest path of all the other vertices
}
void MatrixGraph::getPath(const int d){
// Give the destination d and print out the path
}
int main(){
int start,destination;
cin>>start;
cin>>destination;
MatrixGraph *g = new MatrixGraph(start,destination);
g->ShortestPath(start);
g->getPath(destination);
}
We provide INITIALIZE-SINGLE-SOURCE(G,s) and RELAX(u,v,length) algorithm here. You can use it as a referenece to solve the problem.
INITIALIZE-SINGLE-SOURCE(G,s){
for each vertex v belongs to G.v
dist[v]=infinity
predecessor[v]=NIL
dist[s]=0
}
RELAX(u,v,length){
if dist[v]>dist[u]+length(u,v)
dist[v]=dist[u]+length(u,v)
predecessor[v]=u
}
Input
Start Vertex
Destination Vertex
Output
Distance of shortest path from start vertex to destination vertex
Print out the shortest path(每一個輸出節點之間要有空格，包含最後一個節點後面也必須有空格)(印完記得要換行)
Tags