java - 是否也可以删除加权图中的某些边

Question

我正在阅读 LaFore 的《数据结构和算法》，我遇到了书中提供的这段代码，它使用 Dijkstra 算法来查找最短路径，是否也可以删除顶点或边缘？想知道为什么这本书没有包含删除方法？再次感谢您的帮助!

   package pathapp;

     /**
     *
     *
     */
public class DistPar // distance and parent
{ // items stored in sPath array
public int distance; // distance from start to this vertex
public int parentVert; // current parent of this vertex
// -------------------------------------------------------------

public DistPar(int pv, int d) // constructor
{
distance = d;
parentVert = pv;
}
// -------------------------------------------------------------
} // end class DistPar

public class Vertex
{
public char label; // label (e.g. 'A')
public boolean isInTree;
// -------------------------------------------------------------

public Vertex(char lab) // constructor
{
label = lab;
isInTree = false;
}
// -------------------------------------------------------------
} // end class Vertex


public class Graph
{
private final int MAX_VERTS = 20;
private final int INFINITY = 1000000;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private int nTree; // number of verts in tree
private DistPar sPath[]; // array for shortest-path data
private int currentVert; // current vertex
private int startToCurrent; // distance to currentVert

// -------------------------------------------------------------

public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
nTree = 0;
for(int j=0; j<MAX_VERTS; j++) // set adjacency
for(int k=0; k<MAX_VERTS; k++) // matrix
adjMat[j][k] = INFINITY; // to infinity
sPath = new DistPar[MAX_VERTS]; // shortest paths
} // end constructor
// -------------------------------------------------------------

public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
// -------------------------------------------------------------

public void addEdge(int start, int end, int weight)
{
adjMat[start][end] = weight; // (directed)
}
// -------------------------------------------------------------

public void path() // find all shortest paths
{
int startTree = 0; // start at vertex 0
vertexList[startTree].isInTree = true;
nTree = 1; // put it in tree

// transfer row of distances from adjMat to sPath
for(int j=0; j<nVerts; j++)
{
int tempDist = adjMat[startTree][j];
sPath[j] = new DistPar(startTree, tempDist);
}

// until all vertices are in the tree
while(nTree < nVerts)
{
int indexMin = getMin(); // get minimum from sPath
int minDist = sPath[indexMin].distance;

if(minDist == INFINITY) // if all infinite
{ // or in tree,
System.out.println("There are unreachable vertices");
break; // sPath is complete
}
else
{ // reset currentVert
currentVert = indexMin; // to closest vert
startToCurrent = sPath[indexMin].distance;
// minimum distance from startTree is
// to currentVert, and is startToCurrent
}
System.out.print(startToCurrent + "-> ");
// put current vertex in tree
vertexList[currentVert].isInTree = true;
nTree++;
adjust_sPath();
// update sPath[] array
} // end while(nTree<nVerts)
displayPaths(); // display sPath[] contents

nTree = 0; // clear tree
for(int j=0; j<nVerts; j++)
vertexList[j].isInTree = false;
} // end path()
// -------------------------------------------------------------

public int getMin() // get entry from sPath
{ // with minimum distance
int minDist = INFINITY; // assume minimum
int indexMin = 0;
for(int j=1; j<nVerts; j++) // for each vertex,
{ // if it's in tree and
if( !vertexList[j].isInTree && // smaller than old one
sPath[j].distance < minDist )
{
minDist = sPath[j].distance;
indexMin = j; // update minimum
}
} // end for
return indexMin; // return index of minimum
} // end getMin()
// -------------------------------------------------------------

public void adjust_sPath()
{
// adjust values in shortest-path array sPath
int column = 1; // skip starting vertex
while(column < nVerts) // go across columns
{
// if this column's vertex already in tree, skip it
if( vertexList[column].isInTree )
{
column++;
continue;
}
// calculate distance for one sPath entry
// get edge from currentVert to column
int currentToFringe = adjMat[currentVert][column];
// add distance from start
int startToFringe = startToCurrent + currentToFringe;
// get distance of current sPath entry
int sPathDist = sPath[column].distance;

// compare distance from start with sPath entry
if(startToFringe < sPathDist) // if shorter,
{ // update sPath
sPath[column].parentVert = currentVert;
sPath[column].distance = startToFringe;
}
column++;
} // end while(column < nVerts)
} // end adjust_sPath()
// -------------------------------------------------------------

public void displayPaths()
{
for(int j=0; j<nVerts; j++) // display contents of sPath[]
{
System.out.print(vertexList[j].label + "="); // B=
if(sPath[j].distance == INFINITY)
System.out.print("inf"); // inf
else
System.out.print(sPath[j].distance); // 50
char parent = vertexList[ sPath[j].parentVert ].label;
System.out.print("(" + parent + ") "); // (A)
}
System.out.println("");
}
// -------------------------------------------------------------
} // end class Graph
////////////////////////////////////////////////////////////////

/**
*
*
*/
// path.java
// demonstrates shortest path with weighted, directed graphs
////////////////////////////////////////////////////////////////

public class PathApp {

public static void main(String[] args) {


Graph theGraph = new Graph();

theGraph.addVertex('A'); // 0 (start)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4


theGraph.addEdge(0, 1, 50); // AB 50
theGraph.addEdge(0, 3, 80); // AD 80
theGraph.addEdge(1, 2, 60); // BC 60
theGraph.addEdge(1, 3, 90); // BD 90
theGraph.addEdge(2, 4, 40); // CE 40
theGraph.addEdge(3, 2, 20); // DC 20
theGraph.addEdge(3, 4, 70); // DE 70
theGraph.addEdge(4, 1, 50); // EB 50


System.out.println("Shortest paths");
theGraph.path(); // shortest paths
} // end main()

} // end class PathApp
////////////////////////////////////////////////////////////////

Answer 1

我不明白为什么您期望在程序中使用删除函数来查找最短路径。您始终可以通过将以下函数添加到 Graph 类中来手动从图中删除顶点和边。

public void delete(char V)  //deletes a vertex V
{
    int I=-1;
    for(int i=0;i<nVerts;++i)
    {
        if(vertexList[i].label==V)
        {
            I=i;
            for(int j=i+1;j<nVerts;++j)
            {
                vertexList[j-1]=vertexList[j];
                adjMat[j-1]=adjMat[j];
            }
            nVerts--;
            break;
        }
    }

    for(int i=0;i<nVerts;++i)
        for(int j=I;j<nVerts;++j)
            adjMat[i][j]=adjMat[i][j+1];        
}

public void delete(char u,char v)   //deletes an edge (u,v)
{
    int from=-1,to=-1;

    for(int i=0;i<nVerts;++i)
    {
        if(vertexList[i].label==u)
        from=i;
        if(vertexList[i].label==v)
        to=i;
    }

    adjMat[from][to]=INFINITY;
}